Dijkstras Algorithm

What is Dijkstra's Algorithm?

Dijkstra's algorithm is a graph traversal algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It is widely used in many applications such as transportation networks, routing protocols, and network optimization problems. It was conceived by Dutch computer scientist Edsger W. Dijkstra in 1956.

The algorithm maintains a set of vertices whose shortest distance from the source has already been calculated, and a set of vertices whose shortest distance is yet to be calculated. It then picks the vertex with the shortest distance and updates the distances of its neighbors, repeating until all vertices have been processed. The algorithm returns the shortest path from the source to every other vertex in the graph.

How does Dijkstra's Algorithm work?

Dijkstra's algorithm works by maintaining two sets of vertices:

A set of vertices whose shortest distance from the source has already been calculated.

A set of vertices whose shortest distance is yet to be calculated. Initially, the distance from the source to itself is zero and the distance to all other vertices is infinity. The algorithm then selects the vertex with the smallest distance from the set of vertices whose shortest distance is yet to be calculated. This vertex is added to the set of vertices whose shortest distance has already been calculated.

Next, the algorithm updates the distances of all neighboring vertices of the selected vertex by adding the weight of the edge that connects them. If the new distance is smaller than the current distance, the distance is updated and the vertex is added to the set of vertices whose shortest distance is yet to be calculated.

The algorithm repeats this process until all vertices have been processed. The shortest path from the source to any other vertex in the graph can then be obtained by tracing back the path from the destination vertex to the source vertex using the parent array.

Example

	New York	Los Angeles	London	Paris	Tokyo	Sydney	Dhaka
New York	0	400	600	700	1200	1500	800
Los Angeles	400	0	800	900	1500	1700	1200
London	600	800	0	200	1100	2000	900
Paris	700	900	200	0	1300	2100	1000
Tokyo	1200	1500	1100	1300	0	2500	1800
Sydney	1500	1700	2000	2100	2500	0	2400
Dhaka	800	1200	900	1000	1800	2400	0

Algorithm

The algorithm can be summarized as follows:

1. Create a set of unvisited vertices and assign a tentative distance of infinity to each vertex.
2. Assign a tentative distance of 0 to the source vertex and mark it as visited.
3. For the current vertex, examine its neighbors and calculate their tentative distances.
4. Update the tentative distances of the neighboring vertices if they are smaller than the current tentative distance.
5. Mark the current vertex as visited.
6. Select the unvisited vertex with the smallest tentative distance and set it as the current vertex.
7. Repeat steps 3-6 until all vertices have been visited.

Pseudocode

The pseudocode for Dijkstra's algorithm is as follows:

function Dijkstra(Graph, source):
    dist[source] ← 0
    create vertex set Q

    for each vertex v in Graph:
        if v ≠ source
            dist[v] ← INFINITY
        prev[v] ← UNDEFINED
        add v to Q

    while Q is not empty:
        u ← vertex in Q with min dist[u]
        remove u from Q 

        for each neighbor v of u:   
            alt ← dist[u] + length(u, v)
            if alt < dist[v]
                dist[v] ← alt
                prev[v] ← u

    return dist, prev

Here, dist is an array that stores the tentative distance of each vertex from the source, and prev is an array that stores the parent of each vertex in the shortest path tree.

Implementation

Dijkstra's algorithm can be implemented using various data structures such as arrays, linked lists, heaps, or priority queues. The choice of data structure affects the time and space complexity of the algorithm.

One common implementation of Dijkstra's algorithm uses a priority queue to store the unvisited vertices in increasing order of their tentative distance. This allows the algorithm to quickly find the next vertex to visit and update it as needed:

function dijkstra(graph, source):
    # Initialize distances and parents
    dist = {}
    prev = {}
    for vertex in graph:
        dist[vertex] = float('inf')
        prev[vertex] = None

    # Distance to source vertex is 0
    dist[source] = 0

    # Initialize priority queue with source vertex
    pq = [(dist[vertex], vertex) for vertex in graph]
    heapq.heapify(pq)

    # Main loop
    while pq:
        # Get vertex with smallest tentative distance
        current_dist, current_vertex = heapq.heappop(pq)

        # Skip if already visited
        if current_dist > dist[current_vertex]:
            continue

        # Update distances of neighbors
        for neighbor, weight in graph[current_vertex].items():
            tentative_dist = dist[current_vertex] + weight
            if tentative_dist < dist[neighbor]:
                dist[neighbor] = tentative_dist
                prev[neighbor] = current_vertex
                heapq.heappush(pq, (tentative_dist, neighbor))

    return dist, prev

This implementation uses a dictionary to represent the graph, where each key is a vertex and its value is another dictionary that represents its neighbors and their weights. It also uses a heap data structure to store the unvisited vertices in increasing order of their tentative distance.

Performance

The time complexity of Dijkstra's algorithm depends on the implementation and the data structure used to store the graph and the unvisited vertices. In the worst case, the algorithm takes O(|V|^2) time using an adjacency matrix representation, where |V| is the number of vertices in the graph. However, using a heap-based implementation, the time complexity can be reduced to O(|E| log |V|), where |E| is the number of edges in the graph.

The space complexity of the algorithm is O(|V|) for the distance array and O(|V|) for the parent array, as well as the space required to store the graph and the priority queue.

Comparison to other similar algorithms

Dijkstra's algorithm is similar to other shortest path algorithms such as Bellman-Ford and A* search. Bellman-Ford is more general in that it can handle negative edge weights, but it has a higher time complexity of O(|V| |E|). A* search is a heuristic search algorithm that uses an admissible heuristic to guide the search, but it requires a goal node and may not always find the optimal path.

When should I use this algorithm, pros and cons

Dijkstra's algorithm is ideal for finding the shortest path between a single source and all other vertices in a non-negative weighted graph. It is also suitable for applications where finding the optimal path is critical, such as in transportation networks, routing protocols, and network optimization problems.

Pros:

Guaranteed to find the shortest path Suitable for non-negative weighted graphs Efficient for sparse graphs using a heap-based implementation

Cons:

Inefficient for dense graphs using an adjacency matrix representation Cannot handle negative edge weights May not always find the optimal path in certain cases, such as when there are multiple edges with the same weight Real-life application of it Dijkstra's algorithm is used in various real-life applications, including:

1. GPS navigation systems
2. Routing protocols in computer networks
3. Traffic routing and scheduling in transportation systems
4. Network optimization in telecommunications networks
5. Finding the shortest path between two nodes in a social network

Common questions and answers (interview or exam)

Q: What is the time complexity of Dijkstra's algorithm? A: The time complexity is O(|E| log |V|), where |E| is the number of edges in the graph and |V| is the number of vertices.

Q: What is the difference between Dijkstra's algorithm and Bellman-Ford algorithm? A: Dijkstra's algorithm is suitable for finding the shortest path between a single source and all other vertices in a non-negative weighted graph, while Bellman-Ford algorithm is more general and can handle negative edge weights. However, Bellman-Ford has a higher time complexity of O(|V| |E|) compared to Dijkstra's algorithm using a heap-based implementation.

Q: What data structure is commonly used to implement Dijkstra's algorithm? A: A heap-based priority queue is commonly used to store the unvisited vertices in increasing order of their tentative distance.

Conclusion

Dijkstra's algorithm is a popular shortest path algorithm that finds the optimal path between a single source and all other vertices in a non-negative weighted graph. It is efficient for sparse graphs using a heap-based implementation and has various real-life applications in transportation networks, routing protocols, and network optimization problems. While it cannot handle negative edge weights and may not always find the optimal path in certain cases, it is still a valuable tool in solving graph problems.