graph - ネットワーク内の最寄りの病院

Question

都市を表すグラフがあります。一部の頂点は病院です。グラフがつながりました。

特定のノードから最寄りの病院までのパス (または距離) を提供するアルゴリズムを探しています。

すべての最短経路を計算することを考えることができますが、それらはよりスマートな方法かもしれないと思います.

ありがとう

Answer 1

ウォーシャルの最短パスのアルゴリズムを見る必要があると思います。
ここにアルゴリズムがあります

let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity)
for each vertex v
   dist[v][v] ← 0
for each edge (u,v)
   dist[u][v] ← w(u,v)  // the weight of the edge (u,v)
for k from 1 to |V|
   for i from 1 to |V|
      for j from 1 to |V|
         if dist[i][k] + dist[k][j] < dist[i][j] then
            dist[i][j] ← dist[i][k] + dist[k][j]

上記のアルゴリズムは、左下のグラフで実行されます

[1]: http://i.stack.imgur.com/3J7Sb.png
参照: wikiPedia (リンクは回答の冒頭にあります)
詳細については、リンクを参照してください。