Simplex

Twophase

Dijkstra

Prim

Kruskal

Ford-Fulkerson

最短経路問題

ダイクストラ法

1. 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.
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.
3. Find a vertex v which minimizes {L(v): v in V\S_i}, say u_i+1 .
4. Let S_i+1 = S_i cup {u_i+1}.
5. Replace i by i+1. If i=|V|-1 then stop, otherwise go to step 2.

JavaScript ソースファイル:

• dijkstra.js, graph.js, heap.js

JavaScript デモ:

• a (6,10) graph
• a (16,33) digraph
• a (48,77) graph 徳島県とその周辺
• a (14,22) digraph 徳島とその周辺(2)
• a (9,15) graph 徳島から四国の他の主要地点まで
• a (8,12) graph
• a (6,12) graph
• a (10,19) graph

関連ページ:

• Minimum Spanning Tree by Prim's Algorithm
• Minimum Spanning Tree by Kruskal's Algorithm
• Max Flow by Ford-Fulkerson's Labeling Algorithm
• Simplex Method