Shortest Path is a problem to determine shortest path (has minimal weight) between 2 vertex in a graph. There are several algorithm to solve this problem. In this table below is lists of algorithm that solves Single Source Shortest Path:

On unweighted graph, shortest path problem could be solved with BFS (Breadth First Search).

Due to weight on each edges, using BFS would not give us an optimal result, and the use of another algorithm is needed such as Dijkstra or Bellman-Ford. This module would explain Dijkstra Algorithm only.

Dijkstra Algorithm has many variations. The most used one is to determine shortest path from a source vertex to all of other vertex.

1. Set each distance of vertex with infinity (a big value or an unused value could be used) except distance from source vertex (we set this value with 0).

2. Push vertex source to a min-priority queue (ascending priority queue) formatted (distance, vertex), so that the min-priority queue would sort the distance ascendingly.

3. Pop vertex with shortest distance from priority queue

4. Update distance from vertex that are connected with popped vertex (vertex from the third step) if “distance of current vertex + edge weight < next vertex distance”, then push that vertex.

5. If the popped vertex is already visited, continue.

6. Do the third step until priority queue is empty.

Determine shortest path from vertex A to all vertex.

Initial:

First step:

Second step:

Third step:

Fourth step:

Fifth step:

void dijkstra(vector<long> &result, long start){
    vector<bool> visited(vertexCount, false);
    priority_queue <pair<long, long>, 
                    vector <pair<long, long>>, 
                    greater <pair<long, long>> > pq;
    result = vector<long>(vertexCount, LONG_MAX);
    
    pq.push(make_pair(0, start));
    result[start] = 0;
    /* 
    weight from an edge is placed as the first element of pair, so the priority queue would sort edge based on edge's weight
    */

    while(!pq.empty()){
        auto temp = pq.top();
        pq.pop();

        if(visited[temp.second]) continue;

        visited[temp.second] = true;

        for(auto vertex:adjList[temp.second]){
            long nextVertex = vertex.first;
            long weight = vertex.second;

            if(temp.first + weight < result[nextVertex]) {
                result[nextVertex] = temp.first + weight;
                pq.push(make_pair(result[nextVertex], nextVertex));
            }
        }
    }
}

To Minimum Spanning Tree >