Implementation of Dijkstra's algorithm in C++

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;
}
• Is your code currently working as intended? Please clarify, as it is not clear from the way your question is worded... – Phrancis Apr 25 '16 at 18:13

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) {
}

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(),