Implementation of Dijkstra's algorithm in C++

Question

This is my implementation of Dijkstra's algorithm. Could you tell me what am I doing wrong and what should be fixed? I was not sure how to keep track of the shortest outgoing edge from a node and I store -1 if there weren't any edges found yet. I am not sure if it is okay.

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;
#define MAX_LENGTH 10000
int dijkstra(vector<vector<int>> graph, int source, int target) {
 size_t number_of_nodes = graph.size();
 vector<int> visited;
 map<int, int> lengths_to_nodes; // keeps pairs of lengths like 0:0, 1:20, 2:40
 //fill with max lengths and set source as 0 eg. 0:0 1:10000, 2:10000...
 for (int i = 0; i < number_of_nodes; ++i) {
 lengths_to_nodes.insert(make_pair(i, MAX_LENGTH));
 }
 lengths_to_nodes[source] = 0;
 //set actual node we look path from
 int actual_node = source;
 while (visited.size() < number_of_nodes) {
 //keep track of the shortest path found from this node because it will be
 //the next one we will looking for path from
 //if there was no paths from this node then go back
 int the_shortest_found_now = -1; /*** IS IT OKEY? ***/
 int the_shortest_found_now_length = MAX_LENGTH;
 for (int actual_target = 0; actual_target < number_of_nodes; ++actual_target) {
 if (graph[actual_target][actual_node] > 0) {
 int new_length = graph[actual_target][actual_node] + lengths_to_nodes.find(actual_node)->second;
 if (lengths_to_nodes.find(actual_target)->second > new_length) {
 lengths_to_nodes.find(actual_target)->second = new_length;
 }
 if (new_length < the_shortest_found_now_length) {
 the_shortest_found_now_length = new_length;
 the_shortest_found_now = actual_target;
 }
 }
 }
 if (the_shortest_found_now == -1) {
 //if there was no outgoing edges
 actual_node = *(visited.end() - 1);
 visited.erase(visited.end() - 1, visited.end());
 }
 else {
 actual_node = the_shortest_found_now;
 visited.push_back(the_shortest_found_now);
 }
 }
 return lengths_to_nodes.find(target)->second;
}
int main() {
 vector<vector<int>> graph =
 {{{0, 0, 0, 0, 0, 0, 20, 0,},
 {20, 0, 0, 0, 50, 50, 0, 0,},
 {0, 0, 0, 10, 0, 0, 0, 0,},
 {80, 0, 10, 0, 0, 40, 0, 0,},
 {0, 0, 0, 0, 0, 0, 0, 0,},
 {0, 10, 10, 0, 30, 0, 0, 0,},
 {90, 0, 0, 20, 0, 0, 0, 0,},
 {0, 0, 20, 0, 0, 0, 0, 0,},
 }};
 cout << dijkstra(graph, 0, 7) << endl;
 return 0;
}

• Phrancis: Is your code currently working as intended? Please clarify, as it is not clear from the way your question is worded...

Answer 1

Design

So not really Dijkstra algorithm.

while (visited.size() < number_of_nodes)

This condition may not be met in all graphs (if there is a subset of nodes not connected to other nodes).

Also Dijkstra uses two lists.

1. List of nodes that have been visited. (starts empty)
2. A sorted frontier list.

You have the 1st list but seem to cobbling the second list out of thin air each iteration.

Code Review.

int dijkstra(vector<vector<int>> graph, int source, int target) {

Sure. You are returning the shortest length from source to target. But would it not be more interesting to return the path most of the time.

Also a graph being a vector of vector of int is a bit restrictive. You could have created a concept of a graph. Then templatized the algorithm based on the concept. Then writing a wrapper for vector of vector of int to implement the concept would have been trivial.

// Concept.
Graph
 Node const& getNode(int id) const // returns a reference to a node.
Node
 int edgeCount() const // returns number of outbound edges
 Edge const& getEdge(int id) const // returns a reference to an edge
Edge
 int getDst() const // returns the id of the dst vertices.
 int getCost() const // returns the cost from this node to dst.

Algorith for Dijkstra

template<typename Graph>
vector<int> dijkstra(Graph const& graph, int start, int end)
{
 std::vector<int> seen;
 std::priority_queue<Frontier> frontierList;
 frontierList.push({start, 0, {start}});
 while(!frontierList.empty())
 {
 Frontier head = frontierList.top();
 frontierList.pop();
 if (head.location == end) {
 return head.path.append(end);
 }
 if (std::find(std::begin(seen), std::end(seen), head.location) != std::end(seen)) {
 continue;
 }
 for(int loop=0;loop < graph.getNode(head.location).edgeCount(); ++loop) {
 auto const& edge = graph.getNode(head.location).getEdge(loop);
 frontierList.push({edge.getDst(),
 head.cost + edge.getCost(),
 head.path.append(head.location)});
 }
 }
 return {}; // empty path as none was found.
}

• shrike: Thanks for your code. Could you please detail definition of struct Frontier ?