Dijkstra Alg 能找到所有的最短路径吗？

可以算出最短路径条数，但是不能都输出来

jy02677290 发表于 2013-2-11 00:02
那如果我想用一个DAG来记录两点之间存在的最短路径条数，要怎么记录呢？谢谢！

用一个有向无环图记录最短路径条数？这个DAG是指啥？要求所有点之间两两的路径数？还是求一个点到其他所有点最短路径的条数？

Dijkstra only returns one particular solution. Because when it is a tie on the weight, you are making a choice.

jy02677290 发表于 2013-2-11 02:55
对 DAG是directed acyclic graph
我想用这个DAG的权重记录最短路径的条数，比如上面的例子，那么DAG就是 ...

不明白为什么是DAG，除非原图是DAG才对应DAG啊，不然a->b,b->c,c-a的一个图，怎么能对应一个DAG呢？

如果是原图DAG的话，可以执行N次Dij顺便维护下信息，可以得到一个最短路径数的DAG。复杂度O(n^2logn)

稍微改一下就行啊， 当出现相等的时候， 你把节点的上家都标记出来 （而不是只标记一个可选的上家） 就可以了。
这不会增加算法的复杂度啊。

mark,正在做一个有关的project