可能最短路径不唯一，要得出所有的最短路径，请问有什么办法？
针对带权图或者无权图都可以，没有个思路，谁有思路或者算法提供一个，感恩不尽阿。
8 个解决方案
#1
以前的讨论：
http://topic.csdn.net/t/20040919/11/3387612.html
http://topic.csdn.net/t/20040919/11/3387612.html
#2
不知道是不是我理解错题意了，但是好像medie2005的网址没能给出解决方法吧
#3
就是floyd算法啊
#4
迪杰克斯屈拉算法。为带权图生成一个最短通路。
下面是思路：
设G是带权图，确定从顶点s到G中其他定点的最小通路。
步骤1：将s标记为0，使s没有前驱；
令p={s};
步骤2：（对其他顶点作标记)
将每个不再p中的顶点标记为W(S,V)（可能是暂时的，如果两个点不相连则标记为无穷）
并且是v的前驱是s（可能使暂时的）；
步骤3：（扩大p,修改标记）
repeat
步骤3.1：（使另一个标记永久化）
把不再p中，且带有最小标记的顶点加入到p中去，（如果这样的顶点超过一个，任选一个标记）
步骤3.2：（修改临时标记）
对每个不再p中且和u相邻的顶点x,把x的标记换为下列二者的较小者：x的旧标记，U上的标记与
W(u,x)之和；如果x的标记改变了，则使u成为x的新前驱。（可能是暂时的）
until p包含G的每个顶点
步骤4：（求出最短距离及通路）
顶点y上的标记是s到y的距离，如果顶点y上的标记是无穷，则没有这样的通路，否则逆序打印遍历的节点。
然后再用图的遍历来看有没有其他满足条件的通路
下面是思路：
设G是带权图，确定从顶点s到G中其他定点的最小通路。
步骤1：将s标记为0，使s没有前驱；
令p={s};
步骤2：（对其他顶点作标记)
将每个不再p中的顶点标记为W(S,V)（可能是暂时的，如果两个点不相连则标记为无穷）
并且是v的前驱是s（可能使暂时的）；
步骤3：（扩大p,修改标记）
repeat
步骤3.1：（使另一个标记永久化）
把不再p中，且带有最小标记的顶点加入到p中去，（如果这样的顶点超过一个，任选一个标记）
步骤3.2：（修改临时标记）
对每个不再p中且和u相邻的顶点x,把x的标记换为下列二者的较小者：x的旧标记，U上的标记与
W(u,x)之和；如果x的标记改变了，则使u成为x的新前驱。（可能是暂时的）
until p包含G的每个顶点
步骤4：（求出最短距离及通路）
顶点y上的标记是s到y的距离，如果顶点y上的标记是无穷，则没有这样的通路，否则逆序打印遍历的节点。
然后再用图的遍历来看有没有其他满足条件的通路
#5
lyg_wangyushi 的思路好像能够解决问题，但是还有些不太懂得地方
步骤1-4好像就是dijkstra算法吧？没有做出什么改动以便于求其它最短路径吧
关键是"然后再用图的遍历来看有没有其他满足条件的通路",该怎么实现？
步骤1-4好像就是dijkstra算法吧？没有做出什么改动以便于求其它最短路径吧
关键是"然后再用图的遍历来看有没有其他满足条件的通路",该怎么实现？
#6
最简单的方式，当图很稠密，且最短路径确实很多时，很有效
可以归为A*算法
（1）找出所有点到终点的最短距离 该矩阵记为A ,A[1]就是起始点到终点的最短路径，记为dist = A[1];
(2),开始从图G的起始顶点宽度搜索+分支限界，需要使用一个最小队列，就是用A*算法来搜索所有路径 下面很像disikstra，
假设当前访问点为cur，
计算weight = 已经走过的路的长度 + A[cur]
如果(weight<=dist),那么 把它的后继都放入队列中
否则，将该点放到Close表中，
感觉一时也说不清楚，看看A*算法就可以了，只要把A*中的 预估计值 用这里的A[x]就可以了。
#7
共广度优先遍历图，察看是否有其他权之和合所求得的最小权值之和相同的通路
#8
忘了说，这个是一个NPC问题
#1
以前的讨论：
http://topic.csdn.net/t/20040919/11/3387612.html
http://topic.csdn.net/t/20040919/11/3387612.html
#2
不知道是不是我理解错题意了，但是好像medie2005的网址没能给出解决方法吧
#3
就是floyd算法啊
#4
迪杰克斯屈拉算法。为带权图生成一个最短通路。
下面是思路：
设G是带权图，确定从顶点s到G中其他定点的最小通路。
步骤1：将s标记为0，使s没有前驱；
令p={s};
步骤2：（对其他顶点作标记)
将每个不再p中的顶点标记为W(S,V)（可能是暂时的，如果两个点不相连则标记为无穷）
并且是v的前驱是s（可能使暂时的）；
步骤3：（扩大p,修改标记）
repeat
步骤3.1：（使另一个标记永久化）
把不再p中，且带有最小标记的顶点加入到p中去，（如果这样的顶点超过一个，任选一个标记）
步骤3.2：（修改临时标记）
对每个不再p中且和u相邻的顶点x,把x的标记换为下列二者的较小者：x的旧标记，U上的标记与
W(u,x)之和；如果x的标记改变了，则使u成为x的新前驱。（可能是暂时的）
until p包含G的每个顶点
步骤4：（求出最短距离及通路）
顶点y上的标记是s到y的距离，如果顶点y上的标记是无穷，则没有这样的通路，否则逆序打印遍历的节点。
然后再用图的遍历来看有没有其他满足条件的通路
下面是思路：
设G是带权图，确定从顶点s到G中其他定点的最小通路。
步骤1：将s标记为0，使s没有前驱；
令p={s};
步骤2：（对其他顶点作标记)
将每个不再p中的顶点标记为W(S,V)（可能是暂时的，如果两个点不相连则标记为无穷）
并且是v的前驱是s（可能使暂时的）；
步骤3：（扩大p,修改标记）
repeat
步骤3.1：（使另一个标记永久化）
把不再p中，且带有最小标记的顶点加入到p中去，（如果这样的顶点超过一个，任选一个标记）
步骤3.2：（修改临时标记）
对每个不再p中且和u相邻的顶点x,把x的标记换为下列二者的较小者：x的旧标记，U上的标记与
W(u,x)之和；如果x的标记改变了，则使u成为x的新前驱。（可能是暂时的）
until p包含G的每个顶点
步骤4：（求出最短距离及通路）
顶点y上的标记是s到y的距离，如果顶点y上的标记是无穷，则没有这样的通路，否则逆序打印遍历的节点。
然后再用图的遍历来看有没有其他满足条件的通路
#5
lyg_wangyushi 的思路好像能够解决问题，但是还有些不太懂得地方
步骤1-4好像就是dijkstra算法吧？没有做出什么改动以便于求其它最短路径吧
关键是"然后再用图的遍历来看有没有其他满足条件的通路",该怎么实现？
步骤1-4好像就是dijkstra算法吧？没有做出什么改动以便于求其它最短路径吧
关键是"然后再用图的遍历来看有没有其他满足条件的通路",该怎么实现？
#6
最简单的方式，当图很稠密，且最短路径确实很多时，很有效
可以归为A*算法
（1）找出所有点到终点的最短距离 该矩阵记为A ,A[1]就是起始点到终点的最短路径，记为dist = A[1];
(2),开始从图G的起始顶点宽度搜索+分支限界，需要使用一个最小队列，就是用A*算法来搜索所有路径 下面很像disikstra，
假设当前访问点为cur，
计算weight = 已经走过的路的长度 + A[cur]
如果(weight<=dist),那么 把它的后继都放入队列中
否则，将该点放到Close表中，
感觉一时也说不清楚，看看A*算法就可以了，只要把A*中的 预估计值 用这里的A[x]就可以了。
#7
共广度优先遍历图，察看是否有其他权之和合所求得的最小权值之和相同的通路
#8
忘了说，这个是一个NPC问题