Dijkstra's Algorithm
Dijkstra’s algorithm is for finding the single source shortest path from a starting node to all the other nodes in a connected graph of non-negative weights.
This algorithm operates on the principle of relaxation, where it initially overestimates the distances from each node to the source node, setting these distances as an upper bound.
The distance is calculated as the sum of all the edges from the source node to the particular node.
As a new edge is visited, new paths are found as outgoing edges to other nodes. The distance to these outgoing nodes is updated as the minimum of the old path length and the new path length, thus lowering the upper bound as the estimate of the shortest distance.
The visited node will be added to our set of visited node and the distance distance of the visited node is the distance of the shortest path from the source node.
Dijkstra separates the nodes into visited nodes and unvisited nodes. The frontier nodes are a set of unvisited nodes that act as the barrier between the visited nodes and the other unvisited node. We keep track of the frontier node with the minimum distance and add that node to our set of visited nodes. The distance of the visited node is the shortest distance from the source node because any path from the visited nodes to the unvisited nodes must pass through the frontier nodes and the node that we added to the visited node has the smallest distance.
Frontier Node: An unvisited node that is an edge away from a visited node.
Algorithm
We will use a set to keep track of the visited node. Once a node has been visited we will put the node in the set.
Visited node
A map is used to store distances from the source, initially set to infinity for all nodes.
Step 1: Initialize the distance of the starting node to 0 and all the other nodes to infinity.
Step 2: Visit the source node. For all the adjacent nodes that is at the end of the outgoing edges of the source node that hasn’t been visited:
Then mark the source node as visited.
Step 3: Select the unvisited node with the smallest distance and repeat Step 2 with that node. Continues untill all the nodes has been visited.
Note: As each node is visited, the set of unvisited nodes shrinks, breaking the problem into smaller subproblems.
Note: By marking nodes as visited and excluding them from future checks, the algorithm avoids unnecessary backtracking.
领英推荐
Triangle Inequality
The effectiveness of Dijkstra’s algorithm is based on the triangle inequality, which ensures that the path found is the shortest.
For example, if the direct path from node 0 to node 3 is 6 units (d=6(0->3)) is the shourtest then any alternative route must go through the other frontier nodes eg (d=7(0->1->2)), and since node 3 is the shortest route to any frontier node then:
This illustrates that the shortest path does not involve detours through additional nodes, validating the distances updated and maintained throughout the algorithm’s execution.
from typing import Union, List, Tuple, Dict
from collections import defaultdict
import heapq
Node = Union[int, str]
class Dijkstra:
def __init__(self, edges: List[Tuple[Node, Node, int]]) -> None:
self.adjacent_map = self.__initialize_adjacent_map(edges)
self.distances = self.__initialize_distances(self.adjacent_map)
def __initialize_adjacent_map(self, edges: List[Tuple[Node, Node, int]]) -> Dict[Node, List[Tuple[Node, int]]]:
adjacent_map = defaultdict(list)
for node1, node2, weight in edges:
adjacent_map[node1].append((weight, node2))
adjacent_map[node2].append((weight, node1)) # Assuming the graph is undirected
return dict(adjacent_map)
def __initialize_distances(self, adjacent_map: Dict[Node, List[Tuple[Node, int]]]) -> Dict[Node, int]:
distances = {}
for node in adjacent_map.keys():
distances[node] = float('inf')
return distances
def find_shortest_path(self, start_node: Node) -> Dict[Node, int]:
# This method would implement Dijkstra's algorithm to find the shortest path
# from start_node to all other nodes. This method should return a dictionary
# mapping nodes to their shortest distance from start_node.
distances = self.distances.copy()
visited_nodes = set()
min_heap = []
distances[start_node] = 0
heapq.heappush(min_heap, (0, start_node))
while min_heap:
current_node_distance, current_node = heapq.heappop(min_heap)
if current_node not in visited_nodes:
for adjacent_node_edge_length, adjacent_node in self.adjacent_map[current_node]:
distances[adjacent_node] = min(distances[adjacent_node], current_node_distance + adjacent_node_edge_length)
heapq.heappush(min_heap, (distances[adjacent_node], adjacent_node))
visited_nodes.add(current_node)
return distances
edges = [
(0, 1, 2),
(0, 3, 6),
(1, 2, 5),
(2, 3, 7),
(2, 5, 9),
(2, 4, 6),
(3, 4, 10),
(5, 4, 6)
]
dijkstra = Dijkstra(edges)
dijkstra.find_shortest_path(0)
Limitation of Dijkstra’s Algorithm with Negative?Weights
The algorithm relies fundamentally on the assumption that once the shortest path to a node is determined, it will not change. This is because each successive step in Dijkstra’s algorithm builds on the previous steps, assuming that the previously calculated shortest paths are correct and final.
The algorithm relies that distance of the visited node is the distance from the shortest path from the source node. This is supported by the triangle inequality in which the path of the selected node is the shortest. Any alternative route that tries to reach this node through another frontier node will inherently have a greater distance because it must include the additional path length from the other frontier node to the selected node.
The presence of negative weights disrupts this assumption. A negative weight is sufficiently small that a detour via another frontier node to the visited node could result in a shorter path than previously determined.
Difference between Prims and?Dijkstra
The Dijkstra and Prims algorithm look similar, because they both perform breadth first search and select the minimum distances of unvisited nodes. Lets look at the difference between them.
Distance Calculation:
Prims algorithm gives the tree where all the nodes are connected and the sum of the weights of the edges that connect the node is minimum.
Dijkstra provide the shortest route from the source to each node.
I’d like to thank the following resources which were referenced in this article: