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 &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;map&gt;
#include &lt;algorithm&gt;

using namespace std;

#define MAX_LENGTH 10000

int dijkstra(vector&lt;vector&lt;int&gt;&gt; graph, int source, int target) {
    size_t number_of_nodes = graph.size();
    vector&lt;int&gt; visited;
    map&lt;int, int&gt; 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 &lt; 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() &lt; 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 &lt; number_of_nodes; ++actual_target) {
            if (graph[actual_target][actual_node] &gt; 0) {
                int new_length = graph[actual_target][actual_node] + lengths_to_nodes.find(actual_node)-&gt;second;
                if (lengths_to_nodes.find(actual_target)-&gt;second &gt; new_length) {
                    lengths_to_nodes.find(actual_target)-&gt;second = new_length;
                }
                if (new_length &lt; 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)-&gt;second;
}


int main() {
    vector&lt;vector&lt;int&gt;&gt; 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 &lt;&lt; dijkstra(graph, 0, 7) &lt;&lt; endl;

    return 0;
}
Design

So not really Dijkstra algorithm.

while (visited.size() &lt; 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.


List of nodes that have been visited. (starts empty)
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&lt;vector&lt;int&gt;&gt; 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&amp; getNode(int id) const // returns a reference to a node.

Node
    int edgeCount() const             // returns number of outbound edges
    Edge const&amp; 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&lt;typename Graph&gt;
vector&lt;int&gt; dijkstra(Graph const&amp; graph, int start, int end)
{
    std::vector&lt;int&gt;                seen;
    std::priority_queue&lt;Frontier&gt;   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 &lt; graph.getNode(head.location).edgeCount(); ++loop) {
            auto const&amp; 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.
}