Shortest Path Problem: Dijkstra's Algorithm

Mathematical Programming	Dijkstra's Algorithm
Simplex Twophase Dijkstra Prim Kruskal Ford-Fulkerson Dijkstra JavaScript demos: demo1 demo2 demo3 demo4 demo5 demo6 demo7 demo8 FAQ Japanese/English	Shortest Path Problem Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V. Dijkstra's Algorithm Dijkstra's algorithm is known to be a good algorithm to find a shortest path. Set i=0, S₀= {u₀=s}, L(u₀)=0, and L(v)=infinity for v <> u₀. If \|V\| = 1 then stop, otherwise go to step 2. For each v in V\S_i, replace L(v) by min{L(v), L(u_i)+d_v^u_i}. If L(v) is replaced, put a label (L(v), u_i) on v. Find a vertex v which minimizes {L(v): v in V\S_i}, say u_i+1. Let S_i+1 = S_i cup {u_i+1}. Replace i by i+1. If i=\|V\|-1 then stop, otherwise go to step 2. The time required by Dijkstra's algorithm is O(\|V\|²). It will be reduced to O(\|E\|log\|V\|) if heap is used to keep {v in V\S_i : L(v) < infinity}. JavaScript Source File: dijkstra.js, graph.js, heap.js JavaScript Demos a (6,10) graph a (16,33) digraph a (48,77) graph Tokushima prefecture and its neighbor a (14,22) digraph Tokushima city and its neighbor a (9,15) graph From Tokushima city to other major cities in Shikoku Island a (8,12) graph a (6,12) graph a (10,19) graph See Also Minimum Spanning Tree by Prim's Algorithm Minimum Spanning Tree by Kruskal's Algorithm Max Flow by Ford-Fulkerson's Labeling Algorithm Simplex Method
Kenji Ikeda's Home Page	Last Modified: Tuesday, 01-Sep-2015 11:17:41 JST

Mathematical
Programming

Dijkstra's Algorithm

Simplex

Dijkstra

Dijkstra
JavaScript demos:

FAQ

Japanese/English

Shortest Path Problem

Given a connected graph G=(V,E), a weight d:E->R+ and a fixed vertex s in V, find a shortest path from s to each vertex v in V.

Dijkstra's Algorithm

Dijkstra's algorithm is known to be a good algorithm to find a shortest path.

Set i=0, S₀= {u₀=s}, L(u₀)=0, and L(v)=infinity for v <> u₀. If |V| = 1 then stop, otherwise go to step 2.
For each v in V\S_i, replace L(v) by min{L(v), L(u_i)+d_v^u_i}. If L(v) is replaced, put a label (L(v), u_i) on v.
Find a vertex v which minimizes {L(v): v in V\S_i}, say u_i+1.
Let S_i+1 = S_i cup {u_i+1}.
Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.

The time required by Dijkstra's algorithm is O(|V|²). It will be reduced to O(|E|log|V|) if heap is used to keep {v in V\S_i : L(v) < infinity}.

JavaScript Source File:

dijkstra.js, graph.js, heap.js

JavaScript Demos

a (6,10) graph
a (16,33) digraph
a (48,77) graph Tokushima prefecture and its neighbor
a (14,22) digraph Tokushima city and its neighbor
a (9,15) graph From Tokushima city to other major cities in Shikoku Island
a (8,12) graph
a (6,12) graph
a (10,19) graph

Shortest Path Problem

Dijkstra's Algorithm

JavaScript Source File:

JavaScript Demos

See Also