返回信息流☆─────────────────────────────────────☆
lichking (Lich King) 于 (Sun Nov 23 19:20:33 2008) 提到:
弗洛伊德算法求最短路径时怎么才能输出经过结点的顺序？
☆─────────────────────────────────────☆
VeteranA (老A) 于 (Sun Nov 23 19:43:09 2008) 提到:
【 在 lichking 的大作中提到: 】
: 弗洛伊德算法求最短路径时怎么才能输出经过结点的顺序？
有点抽象~
☆─────────────────────────────────────☆
Vampire (吸血的鬼) 于 (Sun Nov 23 21:05:27 2008) 提到:
设path[i][j]表示 从i到j的最短路径上，j结点的前驱
//initialization
for i from 1 to n
for j from 1 to n
if graph[i][j] != infinity or 0 // there is an edge between i and j
then path[i][j]=i
else path[i][j]=-1
//floyd && path recording
for k from 1 to n
for i from 1 to n
for j from 1 to n
if graph[i][k] + graph[k][j] < graph[i][j]
then graph[i][j] = graph[i][k] + graph[k][j]
path[i][j]=path[k][j]
end_if
最后跟着path数组从后往前输出路径结点
☆─────────────────────────────────────☆
newstar19870 (miemie) 于 (Sun Nov 23 22:52:12 2008) 提到:
【 在 Vampire 的大作中提到: 】
: 设path[i][j]表示 从i到j的最短路径上，j结点的前驱
: //initialization
: for i from 1 to n
: ...................
k循环在最外层把...
☆─────────────────────────────────────☆
Vampire (吸血的鬼) 于 (Sun Nov 23 22:55:29 2008) 提到:
呃……是的，我手误了……-_-#
【 在 newstar19870 的大作中提到: 】
: k循环在最外层把...
☆─────────────────────────────────────☆
newstar19870 (miemie) 于 (Sun Nov 23 23:02:32 2008) 提到:
【 在 Vampire 的大作中提到: 】
: 呃……是的，我手误了……-_-#
path[i][j]=k 也有问题，应该是path[i][j]=p[k][j];
初始化的时候,当节点i到节点j 直接相连 p[i][j]=i,否则p[i][j]=-1
☆─────────────────────────────────────☆
newstar19870 (miemie) 于 (Sun Nov 23 23:08:17 2008) 提到:
输出i到j路径：
k=j;
while(k>=0)
{
cout<<k；
k=p[i][k];
}
☆─────────────────────────────────────☆
wks (cloverprince) 于 (Sun Nov 23 23:48:21 2008) 提到:
弗洛伊德算法貌似不能保存路径。
还得用迪克斯彻算法。
这是一条镜像帖。来源：北邮人论坛 / cpp / #29337同步于 2009/10/4
CPP机器人发帖
[合集] 弗洛伊德
shenlei
2009/10/4镜像同步0 回复
订阅后，新回复会通过你的通知中心匿名送达。
0 条回复
暂无回复 · 你可以订阅本帖等待新回复。