线性时间图算法

Question

给定一个无向graphG = (V，E)，有算法计算任意两个顶点之间最短路径的总数吗？我想我们可以利用Dijkstra的算法。

Answer 1

是的你可以用dijkstra。创建一个数组，该数组存储到任何节点的最短路径总数。算了吧。所有数组成员的初始值为0，除非总计=1，其中s是源。

在dijkstra循环中，当比较节点的最小路径时，如果比较的结果较小，则用当前节点的总数更新该节点的总数组。如果等于，则将该节点的总数组与当前节点的总数相加。

摘自维基百科的伪代码，并作了一些修改：

function Dijkstra(Graph, source):

  create vertex set Q

  for each vertex v in Graph:             // Initialization
      dist[v] ← INFINITY                  // Unknown distance from source to v
      total[v] ← 0                        // total number of shortest path
      add v to Q                          // All nodes initially in Q (unvisited nodes)

  dist[source] ← 0                        // Distance from source to source
  total[source] ← 1                       // total number of shortest path of source is set to 1

  while Q is not empty:
      u ← vertex in Q with min dist[u]    // Source node will be selected first
      remove u from Q 

      for each neighbor v of u:           // where v is still in Q.
          alt ← dist[u] + length(u, v)
          if alt < dist[v]:               // A shorter path to v has been found
              dist[v] ← alt 
              total[v] ← total[u]         // update the total array of that node with the number of total array of current node
          elseif alt = dist[v]
              total[v] ← total[v] + total[u] // add the total array of that node with the number of total array of current node

  return dist[], total[]