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), 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 (5,8) graph
• a (10,19) graph
• a (8,12) graph
• a (6,12) graph
• a (11,22) graph
• a (14,22) graph

関連ページ:

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