具有多条最短路径的最短路问题

Shortest path problem with multiple shortest paths

尽管Dijkstra算法是解决正权单源点最短路问题公认的最好算法,但它仅能求得从源点到指定点的一条最短路径,为了给出从源点到指定点的所有最短路径,通过改进临时标号过程,得到了修正的Dijkstra算法.修正后的算法得到的不再是最短路径树,而是最短路径图.相对于原算法,修正后的算法不仅更加简便,而且应用Yen算法能够按照边数由少到多的顺序罗列出所有的最短路径.

Though Dijkstra algorithm is the best known algorithm to solve the shortest path problem with nonnegative weight, it can only get one path from the source vertex to a designated vertex. In order to present all shortest paths from the source vertex to a designated vertex, the revised Dijkstra algorithm is obtained by im- proving the temporary label updating process. As a result, the revised algorithm gives the shortest path graph other than the shortest path tree. Compared with Dijkstra algorithm, the revised algorithm is simple, and all shortest paths can be given according to the number of edge by applying Yen algorithm.