Shortest Path Algorithm Visualizer
Shortest Path Algorithm Visualizer visualizes Dijkstra’s Algorithm to find the shortest path between two nodes in a weighted graph. Enter nodes, edges, source, and destination to compute and visualize the path.
Methodology Used in Shortest Path Visualizer
Dijkstra’s Algorithm finds the shortest path from a source node to a destination node in a weighted graph with non-negative edge weights:
Algorithm Steps:
1. Initialize distances: Set distance to source = 0, others = ∞.
2. Use a priority queue to select the unvisited node with the smallest distance.
3. Update distances to neighbors if a shorter path is found.
4. Mark node as visited and repeat until destination is reached.
Mathematical Formulation:
\\[ \text{distance}[s] \gets 0, \quad \text{distance}[\text{others}] \gets \infty \\] \\[ \text{For each node } u \text{ selected from priority queue}: \\] \\[ \text{For each neighbor } v \text{ of } u: \\] \\[ \text{if } \text{distance}[u] + w(u,v) < \text{distance}[v]: \\] \\[ \text{distance}[v] \gets \text{distance}[u] + w(u,v) \\] \\[ \text{previous}[v] \gets u \\]Example Calculation
Sample Input
Nodes: A,B,C; Edges: A-B-4, B-C-1; Source: A; Destination: C
Initialize distances:
\\[ d[A] = 0, \quad d[B] = \infty, \quad d[C] = \infty \\]Visit node A, update neighbors:
\\[ d[B] = 0 + 4 = 4 \\]Visit node B, update neighbors:
\\[ d[C] = 4 + 1 = 5 \\]Visit node C:
Destination reached. Shortest path: \\( A \rightarrow B \rightarrow C \\), Distance: \\( 5 \\).