Dijkstra in C++ to find shortest path for every vertex of a directed graph I am trying to implement the Dijkstra algorithm in C++ that finds the shortest path for a graph from a text file. The text file contains a matrix that represents a directed graph. 

What I am trying to do in this code is use every vertex as the source. I finished the code but I am still very skeptical if my code is right or not.

int minDistance(int dist[], bool sptSet[], int V)
{
// Initialize min value
int min = INT_MAX, min_index;

for (int v = 0; v &lt; V; v++)
    if (sptSet[v] == false &amp;&amp; dist[v] &lt;= min)
        min = dist[v], min_index = v;

return min_index;}
double  dijkstra(int vertex, int **graph, int src)
{
auto start_time = chrono::high_resolution_clock::now();
int* dist = new int[vertex];     // The output array.  dist[i] will hold the shortest
// distance from src to i

bool* sptSet = new bool[vertex]; // sptSet[i] will true if vertex i is included in shortest
// path tree or shortest distance from src to i is finalized


src = k;
// Initialize all distances as INFINITE and stpSet[] as false
for (int i = 0; i &lt; vertex; i++)
    {
    dist[i] = INT_MAX, sptSet[i] = false;
    }

// Distance of source vertex from itself is always 0
dist[src] = 0;

// Find shortest path for all vertices
    for (int count = 0; count &lt; vertex - 1; count++)
    {
    // Pick the minimum distance vertex from the set of vertices not
    // yet processed. u is always equal to src in first iteration.
    int u = minDistance(dist, sptSet, vertex);

    // Mark the picked vertex as processed
    sptSet[u] = true;

    // Update dist value of the adjacent vertices of the picked vertex.
    for (int v = 0; v &lt; vertex; v++)

        // Update dist[v] only if is not in sptSet, there is an edge from 
        // u to v, and total weight of path from src to  v through u is 
        // smaller than current value of dist[v]
        if (!sptSet[v] &amp;&amp; graph[u][v] &amp;&amp; dist[u] != INT_MAX &amp;&amp; dist[u] + graph[u][v] &lt; dist[v])
        {
        dist[v] = dist[u] + graph[u][v];
        }
    }
k++;
delete[] dist;
delete[] sptSet;
}


auto end_time = chrono::high_resolution_clock::now();
double elapsed = chrono::duration_cast&lt;chrono::milliseconds&gt;(end_time - start_time).count();

return elapsed;
}
I'm sure it'll be fairly easy for you to confirm if your code is working (you can find test cases all over the place), so I'm not looking too closely at correctness, so much as overall logic.

So, on the whole, it seems to make logical sense, but it's not an efficient implementation of Dijkstra. As you know, Dijkstra's algorithm involves having an ever increasing collection of nodes and picking the smallest path out of your collection (it's that simple).

The main flaw is in your minDistance() method. What you're doing there is effectively iterating over all the nodes you've selected and finding the shortest part out. That's an O(n) operation. This step in Dijkstra is crucial and should be done in O(log N) time. This can be done using a set or a heap. Since you always want the minimum path out, all you need to do is keep track of the paths out and pick the min at each stage.

As I mentioned, you can do this with a set/heap. I think this example should help clear this up.