|
Simplex
Twophase
Dijkstra
Prim
Kruskal
Ford-Fulkerson
Dijkstra
Java applet 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, S0= {u0=s},
L(u0)=0, and L(v)=infinity for v <> u0.
If |V| = 1 then stop, otherwise go to step 2.
- For each v in V\Si, replace L(v) by
min{L(v), L(ui)+dvui}.
If L(v) is replaced, put a label (L(v), ui) on v.
- Find a vertex v which minimizes {L(v): v in V\Si}, say ui+1.
- Let Si+1 = Si cup {ui+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|2).
It will be reduced to O(|E|log|V|)
if heap is used to keep {v in V\Si : L(v) < infinity}.
Java Source File:
Java Applet Demos
- a (6,10) graph
- a (16,33) graph
- a (12,23) graph
- a (16,33) digraph
- a (9,15) graph From Tokushima city to other major cities in Shikoku Island
- a (48,77) graph In Tokushima prefecture and its neighbor
- a (8,12) graph
- a (6,12) graph
- a (10,19) graph
- a (14,22) graph
See Also
|