Dijkstra’s Algorithm#

Welcome to Day 43 of our 60 Days of Coding Algorithm Challenge! Today, we’ll explore Dijkstra’s Algorithm, a fundamental graph algorithm used for finding the shortest paths between nodes in a graph.

What is Dijkstra’s Algorithm?#

Dijkstra’s Algorithm is a greedy algorithm that solves the single-source shortest path problem for a graph with non-negative edge weights. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years later.

How Dijkstra’s Algorithm Works#

1. Initialize distances to all vertices as infinite and distance to the source as 0.
2. Create a set of unvisited vertices.
3. For the current vertex, consider all its unvisited neighbors and calculate their tentative distances.
4. When we are done considering all neighbors of the current vertex, mark it as visited and remove it from the unvisited set.
5. If the destination vertex has been marked visited, we’re done.
6. Otherwise, select the unvisited vertex with the smallest tentative distance, and repeat from step 3.

Implementation#

Let’s implement Dijkstra’s Algorithm in Python:

 1import heapq
 2
 3def dijkstra(graph, start):
 4    distances = {vertex: float('infinity') for vertex in graph}
 5    distances[start] = 0
 6    pq = [(0, start)]
 7    previous = {vertex: None for vertex in graph}
 8
 9    while pq:
10        current_distance, current_vertex = heapq.heappop(pq)
11
12        # If we have already found a shorter path, continue
13        if current_distance > distances[current_vertex]:
14            continue
15
16        for neighbor, weight in graph[current_vertex].items():
17            distance = current_distance + weight
18            if distance < distances[neighbor]:
19                distances[neighbor] = distance
20                previous[neighbor] = current_vertex
21                heapq.heappush(pq, (distance, neighbor))
22
23    return distances, previous
24
25def shortest_path(graph, start, end):
26    distances, previous = dijkstra(graph, start)
27    path = []
28    current_vertex = end
29    while current_vertex is not None:
30        path.append(current_vertex)
31        current_vertex = previous[current_vertex]
32    path.reverse()
33    return path, distances[end]
34
35# Example usage
36graph = {
37    'A': {'B': 4, 'C': 2},
38    'B': {'A': 4, 'C': 1, 'D': 5},
39    'C': {'A': 2, 'B': 1, 'D': 8, 'E': 10},
40    'D': {'B': 5, 'C': 8, 'E': 2, 'F': 6},
41    'E': {'C': 10, 'D': 2, 'F': 3},
42    'F': {'D': 6, 'E': 3}
43}
44
45start = 'A'
46end = 'F'
47path, distance = shortest_path(graph, start, end)
48print(f"Shortest path from {start} to {end}: {' -> '.join(path)}")
49print(f"Total distance: {distance}")

Time Complexity#

The time complexity of Dijkstra’s algorithm depends on the data structure used for the priority queue:

• Using a binary heap: O((V + E) log V), where V is the number of vertices and E is the number of edges.
• Using a Fibonacci heap: O(E + V log V)

Space Complexity#

O(V), where V is the number of vertices in the graph.

Advantages of Dijkstra’s Algorithm#

1. Efficiently finds the shortest path in weighted graphs
2. Works well for graphs with non-negative edge weights
3. Can be used to find shortest paths from a single source to all other vertices

Limitations#

1. Does not work with graphs containing negative edge weights
2. May not find the shortest path in graphs with negative cycles

Applications#

1. GPS and navigation systems
2. Network routing protocols
3. Social network analysis
4. Robotics and path planning

Variations and Optimizations#

1. Bidirectional Dijkstra’s algorithm: Searches from both the start and end vertices simultaneously
2. A* algorithm: Uses heuristics to guide the search towards the goal
3. Johnson’s algorithm: For graphs with negative edge weights but no negative cycles

Exercise#

1. Implement Dijkstra’s algorithm using an adjacency matrix instead of an adjacency list.
2. Modify the algorithm to handle directed graphs.
3. Implement a variation of Dijkstra’s algorithm that finds the path with the maximum flow capacity between two vertices in a flow network.

Summary#

Today, we explored Dijkstra’s Algorithm, a fundamental graph algorithm for finding shortest paths. We implemented the algorithm, discussed its time and space complexity, and looked at its advantages, limitations, and real-world applications.

Understanding Dijkstra’s Algorithm is crucial for solving many graph-related problems and has wide-ranging applications in computer science and beyond.

Solution#

 1def dijkstra_matrix(matrix, start):
 2    n = len(matrix)
 3    INF = float('infinity')
 4    dist = [INF] * n
 5    dist[start] = 0
 6    visited = [False] * n
 7
 8    for _ in range(n):
 9        # Pick the unvisited vertex with the smallest tentative distance
10        u = -1
11        for v in range(n):
12            if not visited[v] and (u == -1 or dist[v] < dist[u]):
13                u = v
14        if u == -1 or dist[u] == INF:
15            break
16        visited[u] = True
17        # Relax all edges out of u (matrix[u][v] == 0 means no edge)
18        for v in range(n):
19            w = matrix[u][v]
20            if w > 0 and not visited[v] and dist[u] + w < dist[v]:
21                dist[v] = dist[u] + w
22    return dist
23
24# Example usage
25# Vertices 0..4; 0 entries mean "no edge"
26matrix = [
27    [0, 4, 2, 0, 0],
28    [4, 0, 1, 5, 0],
29    [2, 1, 0, 8, 10],
30    [0, 5, 8, 0, 2],
31    [0, 0, 10, 2, 0],
32]
33print(dijkstra_matrix(matrix, 0))  # [0, 3, 2, 8, 10]