线性时间图算法

Question

给定一个无向图G = (V,E)，是否有一种算法可以计算两个任意顶点u & v 之间的最短路径总数？我想我们可以利用 Dijkstra 算法。

Answer 1

是的，您可以使用 dijkstra。创建一个数组，用于存储到任何节点的最短路径总数。称之为总。所有数组成员的初始值为 0，除了 total[s] = 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[]

线性时间图算法

Linear time Graph algorithm

algorithm

graph

breadth-first-search

shortest-path

depth-first-search