给定一个无向（无长度）图 G=(V,E)，|V|=n 和 |E|= m，以及两个顶点 v,w，求输出 G 中最短 vw 路径数的算法。运行时间应该是 O(m+n)
我一直在解决这个问题，但很难让运行时间为 O(m+n)
由于该图既是无向图又是未加权的，因此我尝试过这种方式。使用 BFS 确定最短 vw-path 的长度。然后使用 DFS 找到 vw-shortest 路径的数量，使得两个节点连接并且路径的长度等于 BFS 的输出。但是这个计划的运行时间是O(m+n)+O(m+n)。
我还尝试修改 Dijkstra 算法。当有一个节点加入到访问节点集合中时，存储最短路径的长度和最短路径的数量。而且我坚持计算运行时间。
这个问题可能正在寻找Dijsktra's algorithm的修改。使用 Dijkstra 算法，您可以为每个节点维护到该节点的最短路径的长度，然后根据到相邻节点的最短路径和从该相邻节点到该节点的简单链接的长度在节点处更新它有问题。
在每个节点上，您可以保留到它的最短路径的长度，可以在它之前的最短路径上的节点表，以及到该节点的最短路径的数量，这应该是总和到这些邻居的最短路径的数量。当您找到到某个节点的新最短路径时，您要么删除所有这些信息（如果新的最短路径比以前短），要么更新该表中路径中倒数第二个节点的条目，如果新路径是与之前到该节点的最短路径的长度相同。
您可以在 O(N) 中使用修改后的 BFS 找到不同路径的数量。这是解决方案。