网络中最近的医院

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

Reference:wikiPedia (在答案的开头给出链接)

欲知更多详情，请浏览连结。