dijkstra's algorithm Archives - NY Comdori Computer Science Note

Dijkstra’s algorithm is the most popular algorithm to find the shortest paths from a certain vertex in a weighted graph.
In fact, the algorithm will find the shortest paths to every vertex from the start vertex.
The algorithm takes both greedy and dynamic programming approach that it will try to find local optimum paths first and use them to find the shortest paths.
Let’s take a look at how it works!

How does Dijkstra’s algorithm work?

Let’s say we need to find the shortest path from node A to node E.

There are five nodes and each edge is weighted with the cost to traverse from a node to a node.
For example, it costs 5 to traverse from node A to B.

What would be the most efficient way to find out the shortest path?
In order to find the shortest path from node A to E, we need to find out what is the shortest path to nodes that are right before E – A, B, D.
Can you see where we are going?
In order to find out the shortest path to nodes B, D (I skipped A since it’s the start node), we need to find the shortest path to nodes right before – A, C.

Let’s take a look at each step.

From node A, we can reach to nodes B, C, D, and E.
But let’s start with the nodes B and C first.
What is the shortest path from A to B? There is only one path and it costs 5.
What is the shortest path from A to C? There is only one path and it costs 1.
The nodes B and C are very simple but it’s very important because this will be stepping stone to find the shortest paths to further nodes.

Now, based on the shortest paths to the node C, we can find out the shortest path from the node A to the node D.
There are two paths – A to D directly and A to C to D.
As we can see the shortest path from A to D is A -> C -> D with the total cost 3.

Finally, we have found all the shortest paths from A to B, C, and D which are the nodes right before E.
Based on the shortest paths we found so far, we just need to find which is the cheapest way to reach to E.

There are a total of four possible routes from A to E.

A -> E : 10
A -> B -> E : 11
A -> D -> E : 9
A -> C -> D -> E : 8

The shortest path from A to E is A -> C -> D -> E with the cost 8.

The graph itself is pretty simple.
However, the steps we took to find the shortest path is like this.
It really finds the shortest paths to adjacent nodes of A then builds the path based on previous best paths each round.

Start from the start node A
Just like breadth-first search, find shortest paths to adjacent nodes which are B, C, D, and E.
Make sure you keep track of those records.
From nodes B, C, and D, find the shortest path to the node E.

Code Example

This code example has the implementation of Dijkstra’s algorithm which uses the graph in the above example.

#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>

using namespace std;

struct Edge
{
    int destNodeId;
    int weight;
    
    Edge(int _destNodeId, int _weight) : 
        destNodeId(_destNodeId), weight(_weight)
    {}
};

struct Node
{
    // node id which is index of vector in this case
    int nodeId;
    
    // set of edges belong to this node
    vector<Edge> edges;

    // indicates if the node is processed - the shortest path found.    
    bool processed;
    
    Node(int _nodeId, vector<Edge> _edges) : 
        nodeId(_nodeId), edges(_edges), processed(false)
    {}
};

struct Graph
{
    // list of nodes in this graph
    vector<Node> nodes;
    
    // indicates the shortest paths up to this node so far.
    vector<int> shortestDistSoFar;
    
    // indicates parent node id for each node id, which is represented by index
    vector<int> parentNodes;
};

void initializeGraph(Graph &graph)
{
    // initialize node A
    vector<Edge> edges;
    edges.emplace_back(1, 5);
    edges.emplace_back(2, 1);
    edges.emplace_back(3, 4);
    edges.emplace_back(4, 10);
    
    graph.nodes.emplace_back(0, edges);
    
    // initialize node B
    edges.clear();
    edges.emplace_back(4, 6);
    
    graph.nodes.emplace_back(1, edges);
    
    // initialize node C
    edges.clear();
    edges.emplace_back(3, 2);
    
    graph.nodes.emplace_back(2, edges);
    
    // initialize node D
    edges.clear();
    edges.emplace_back(4, 5);
    
    graph.nodes.emplace_back(3, edges);
    
    // initialize node E
    edges.clear();
    graph.nodes.emplace_back(4, edges);
    
    graph.shortestDistSoFar.resize(5, numeric_limits<int>::max());
    graph.parentNodes.resize(5, -1);
}

vector<Node> dijkstra(Graph &graph, int startNodeId)
{
    int currNodeId = startNodeId;
    // distance from A to A is 0
    graph.shortestDistSoFar[currNodeId] = 0;
    // A doesn't have the parent node
    graph.parentNodes[currNodeId] = 0;

    while (!graph.nodes[currNodeId].processed)
    {
        graph.nodes[currNodeId].processed = true;
        
        // take a look at adjacent nodes
        for_each(
            graph.nodes[currNodeId].edges.begin(),
            graph.nodes[currNodeId].edges.end(),
            [&graph, currNodeId](const Edge &destNodeEdge)
            {
                // an adjacent node from current node being processed
                int destNodeId = destNodeEdge.destNodeId;
                
                // weight of the edge
                int weight = destNodeEdge.weight;
                
                // if this is shorter than the record, update it
                if (graph.shortestDistSoFar[currNodeId] + weight < graph.shortestDistSoFar[destNodeId])
                {
                    graph.parentNodes[destNodeId] = currNodeId;
                    graph.shortestDistSoFar[destNodeId] = graph.shortestDistSoFar[currNodeId] + weight;
                }
            });
            
        // find next node to process
        // need to process shortest distance first
        int minDistSoFar = numeric_limits<int>::max();
        for_each(
            graph.nodes.begin(),
            graph.nodes.end(),
            [&currNodeId, &graph, &minDistSoFar](const Node &node)
            {
                if (!node.processed && graph.shortestDistSoFar[node.nodeId] < minDistSoFar)
                {
                    minDistSoFar = graph.shortestDistSoFar[node.nodeId];
                    currNodeId = node.nodeId;
                }
            });
    }
    
    vector<Node> shortestPath;
    
    // need to find shortest path by recursively tracking parent node
    
    currNodeId = 4;
    while (graph.parentNodes[currNodeId] != currNodeId)
    {
        shortestPath.push_back(graph.nodes[currNodeId]);
        currNodeId = graph.parentNodes[currNodeId];
    }
    
    // make sure A is in the path
    shortestPath.push_back(graph.nodes[0]);
    reverse(shortestPath.begin(), shortestPath.end());
    return shortestPath;
}

int main()
{
    Graph graph;
    initializeGraph(graph);
    
    // dijkstra from A of which node id is 0
    vector<Node> shortestPath = dijkstra(graph, 0);
    
    for_each(
        shortestPath.begin(),
        shortestPath.end(),
        [](const Node &node)
        {
            switch (node.nodeId)
            {
            case 0:
                cout << "A -> ";
                break;
            case 1:
                cout << "B -> ";
                break;
            case 2:
                cout << "C -> ";
                break;
            case 3:
                cout << "D -> ";
                break;
            case 4:
                cout << "E ";
                break;
            }
        });
    cout << endl;
    return 0;
}

Performance

Time complexity: O(n^2)
It’s because the algorithm needs to visit each node to find the shortest path.
(You can simply find out there is nested loop)

Conclusion

The algorithm works correctly as long as there aren’t any negative weight edges.
The reason is that the huge negative edge may change the shortest path record to certain edge which was already processed.
But I assume there won’t be many cases that graph will have negative edges.
Thank you for reading the post and please let me know if you have any questions/suggestions.