给定一个无向（无长度）图G=（V，E），其中|V|=n和|E|=m，以及两个顶点V，w，找到输出G中最短V-w-路径数的算法。运行时间应为O（m+n）
我一直在处理这个问题，但很难让运行时间为O（m+n）
由于这张图是无向图和无权重图，我尝试了这种方法。使用BFS来确定最短v-w-路径的长度。然后使用DFS来找到v-w-最短路径的数量，使得两个节点连接并且路径的长度等于BFS的输出。但是这个计划的运行时间是O（m+n）+O（m+n）。
此外，我还试图修改Dijkstra算法。当有节点添加到访问节点集时，存储最短路径的长度和最短路径数。我一直在计算运行时间。
这个问题可能是在寻找对Dijsktra算法的修改。使用Dijkstra的算法，您可以为每个节点维护到该节点的最短路径的长度，并根据到相邻节点的最长路径和从该相邻节点到相关节点的简单链路的长度在节点处更新该长度。
在每个节点上，你可以保留一个最短路径的长度，一个在最短路径上可以在它之前的节点表，以及到该节点的最短路径数，它应该是到这些邻居的最短道路数的总和。当您找到到某个节点的新最短路径时，您可以删除所有这些信息（如果新的最短路径比以前短），或者更新该表中路径中倒数第二个节点的条目（如果新路径与该节点的前一个最短路径长度相同）。
您可以在O（N）中使用修改的BFS找到不同路径的数量。这是解决方案。