graph - 网络中最近的医院

Question

我有一个代表一个城市的图表。一些顶点是医院。该图已连接。

我正在寻找一种算法，它可以为我提供从任何给定节点到最近医院的路径（甚至距离）。

人们可以考虑计算所有最短路径，但我认为它们可能是一种更聪明的方法。

谢谢

Answer 1

我想您需要查看warshall 的最短路径算法。
这是算法

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 （链接在答案的开头）
更多详细信息请访问链接