Single-Source Shortest Paths Algorithm - Dijkstra's Algorithm

• Dijkstra’s Algorithm
• Working Principle of Dijkstra
• Dijkstra Implementation in C++
• Algorithm Explanation
• Time Complexity of Dijkstra’s Algorithm
• Space Complexity of Dijkstra’s Algorithm
• Applications of Dijkstra’s Algorithm
• Run C Programming Online Compiler

Consider you’re at home and want to navigate to a nearby restaurant. Almost instantaneously, your GPS system provides you with the fastest route to your dinner! Your GPS system uses Dijkstra's algorithm as core algorithm to calculate the shortest path from your home to the restaurant. The GPS system represents locations (like your home, and restaurant) as nodes and the roads connecting these locations as edges. The distances or travel times along these roads are the weights.

Dijkstra’s algorithm has numerous real-world applications, such as finding the shortest paths in Google Maps and network routing.

¶Dijkstra’s Algorithm

Dijkstra’s algorithm is a pathfinding algorithm. It’s a simple yet powerful algorithm used to find the shortest paths between nodes in a graph when path cost is non-negative. Imagine you’re at point A and you want to get to point B. There are multiple routes you can take, some longer than others. Dijkstra’s algorithm works by visiting each of these routes, and updating the paths by the shortest one it has found so far. It is also called the Single-Source Shortest Paths Algorithm since it finds all the shortest paths starting from a single node.

Here, suppose our destination is node 7 from node 1. Among the potential shortest paths, we highlight the one with a total cost of 10, marked by red-colored edges. We initially journey from node 1 to node 2, incurring a cost of 7. Continuing, we advance to node 5, resulting in a total cost of 8. Progressing further to node 4, our cumulative cost increases to 9, until finally arriving at node 7 with a concluding cost of 10.

¶Working Principle of Dijkstra

The algorithm works in few steps sequentially,

1. Initialization: The algorithm starts at the node where the journey begins (the source node) and sets the distance to zero. It sets the initial distance for all other nodes as infinity, indicating that we don’t yet know the shortest path to these nodes.

2. Visiting Nodes: The algorithm visits each node, starting with the one with the shortest known distance from the source. It calculates the distance from the source to each of its neighboring nodes and updates their distances if it finds a shorter path.

3. Updating Distances: The algorithm then moves to the next node with the shortest known distance and repeats the process, updating distances as it goes. This continues until it has visited all nodes and found the shortest path to each one.

4. Finding the Shortest Path: Once all the nodes have been visited, the algorithm has found the shortest path from the source to each node. To find the shortest path to a specific destination, it traces back through the nodes from the destination to the source, following the path with the shortest distances.

¶Dijkstra Implementation in C++

#include <iostream>
#include <vector>
#include <set>
#include <limits>

using namespace std;

// Define the adjacency list type for convenience
typedef vector<vector<pair<int, int>>> AdjacencyList;

// Dijkstra's algorithm using a set
vector<int> dijkstra(const AdjacencyList& graph, int start) {
    int n = graph.size(); 
    vector<int> dist(n, numeric_limits<int>::max()); // Distance from start to each node
    dist[start] = 0;

    set<pair<int, int>> activeVertices; // Set to manage nodes
    activeVertices.insert({0, start});

    while (!activeVertices.empty()) {
        int where = activeVertices.begin()->second;
        activeVertices.erase(activeVertices.begin());

        for (auto edge : graph[where]) {
            if (dist[edge.first] > dist[where] + edge.second) {
                activeVertices.erase({dist[edge.first], edge.first});
                dist[edge.first] = dist[where] + edge.second;
                activeVertices.insert({dist[edge.first], edge.first});
            }
        }
    }

    return dist;
}

int main() {
    int nodes = 7, edges = 10;
    AdjacencyList graph(nodes + 1); // +1 to handle 1-based indexing

    // Hardcoded input
    vector<vector<int>> input = {
        {1, 2, 7},
        {1, 3, 11},
        {2, 5, 1},
        {2, 4, 3},
        {3, 4, 1},
        {3, 6, 3},
        {4, 5, 1},
        {4, 7, 1},
        {5, 7, 11},
        {6, 7, 5}
    };

    for (auto& edge : input) {
        int u = edge[0], v = edge[1], w = edge[2];
        graph[u].push_back(make_pair(v, w));
        graph[v].push_back(make_pair(u, w)); // Assuming undirected graph
    }

    int startVertex = 1;

    vector<int> shortestDistances = dijkstra(graph, startVertex);

    cout << "Shortest distances from vertex " << startVertex << ":\n";
    for (int i = 1; i <= nodes; ++i) {
        cout << "To " << i << " : ";
        if (shortestDistances[i] == numeric_limits<int>::max()) {
            cout << "unreachable";
        } else {
            cout << shortestDistances[i];
        }
        cout << "\n";
    }

    return 0;
}

¶Algorithm Explanation

Let’s see how Dijkstra’s Algorithm works step-by-step with the following graph.

1. Initialization:
   

Start Node: 1
Initial Distances: [infinity, 0, infinity, infinity, infinity, infinity, infinity, infinity] (with 1-based indexing)
Active Vertices Set: {(0, 1)} (distance, node)

2. Iteration 1:
   

Current Node: 1
Active Vertices Set: {}
Update distances:
To 2 via 1: 0 + 7 = 7
To 3 via 1: 0 + 11 = 11
New Active Vertices Set: {(7, 2), (11, 3)}
Distances: [inf, 0, 7, 11, inf, inf, inf, inf]

3. Iteration 2:

Current Node: 2
Active Vertices Set: {(11, 3)}
Update distances:
To 5 via 2: 7 + 1 = 8
To 4 via 2: 7 + 3 = 10
New Active Vertices Set: {(8, 5), (10, 4), (11, 3)}
Distances: [inf, 0, 7, 11, 10, 8, inf, inf]

4. Iteration 3:
   

Current Node: 5
Active Vertices Set: {(10, 4), (11, 3)}
Update distances:
To 7 via 5: 8 + 11 = 19 (not better than current infinity)
Distances: [inf, 0, 7, 11, 10, 8, inf, inf]

5. Iteration 4:
   

Current Node: 4
Active Vertices Set: {(11, 3)}
Update distances:
To 7 via 4: 10 + 1 = 11
To 3 via 4: 10 + 1 = 11 (not an improvement)
New Active Vertices Set: {(11, 3), (11, 7)}
Distances: [inf, 0, 7, 11, 10, 8, inf, 11]

6. Iteration 5:

Current Node: 3
Active Vertices Set: {(11, 7)}
Update distances:
To 6 via 3: 11 + 3 = 14
New Active Vertices Set: {(11, 7), (14, 6)}
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]

7. Iteration 6:
   

Current Node: 7
Active Vertices Set: {(14, 6)}
No distance updates (already optimal).
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]

8. Iteration 7:
   

Current Node: 6
Active Vertices Set: {}
No distance updates (already optimal).
Distances: [inf, 0, 7, 11, 10, 8, 14, 11]

This traces how the algorithm systematically explores the graph, continually updating the shortest paths from the start node to all other nodes based on the current known shortest paths. Each step ensures the algorithm only revisits a node if a shorter path to it is discovered, efficiently managing the active set for optimal updates.

¶Time Complexity of Dijkstra’s Algorithm

Dijkstra’s algorithm implemented with a set has a time complexity of O((V + E) log V), where V is the number of vertices and E is the number of edges. Using a priority queue, the time complexity remains the same. In both cases, each vertex is processed at most once, and the priority queue operations take logarithmic time. The choice between a set and a priority queue depends on the specific requirements of the application, with sets offering simplicity and priority queues potentially providing faster execution.

¶Space Complexity of Dijkstra’s Algorithm

The space complexity of Dijkstra’s algorithm is O(V), where V is the number of vertices in the graph. This space complexity arises from the need to store the distance array. Additionally, auxiliary data structures such as the priority queue or set used for managing vertices may also contribute to space usage, but they typically have a smaller impact compared to the distance array. Overall, the space complexity of Dijkstra’s algorithm is linear with respect to the number of vertices in the graph.

¶Applications of Dijkstra’s Algorithm

1. Navigation Systems: GPS devices and mapping applications like Google Maps use Dijkstra’s algorithm to find the shortest route between a starting point and a destination. This is essential for providing accurate and efficient navigation instructions to users.

2. Network Routing: Dijkstra’s algorithm is used in the routing protocols that govern the forwarding of IP packets across the Internet. For example, Interior Gateway Protocols (IGPs) like OSPF (Open Shortest Path First) and IS-IS (Intermediate System to Intermediate System) use Dijkstra’s algorithm to calculate the shortest paths within an autonomous system (AS).

3. **Flight Path Planning: **Airlines and air traffic controllers use Dijkstra’s algorithm to plan flight paths for aircraft, considering factors such as distance, air traffic, and weather conditions. This helps optimize flight routes, minimize fuel consumption, and ensure safety.

4. Robotics and Autonomous Vehicles: Dijkstra’s algorithm is employed in robotics and autonomous vehicle navigation systems to plan optimal paths for robots and vehicles to move from one location to another while avoiding obstacles and hazards.

5. Telecommunications: Telecommunication companies use Dijkstra’s algorithm to optimize the routing of data packets through communication networks, ensuring efficient transmission and minimizing latency.

6. Supply Chain Management: In logistics and supply chain management, Dijkstra’s algorithm is used to optimize transportation routes for goods and materials, minimizing costs and delivery times.

¶Run C Programming Online Compiler

To make your learning more effective, exercise the coding examples in the text editor below.

Run C programming online