无向图的最大路问题
请各位大虾解决个问题，有些oi题需要求无向图的最长路，但是如果把求最短路的Dijkstra反过来用无法处理环的问题，请问下哪位朋友知道有效的解决办法，最好附上主过程(Pascal为上，C也可).
无向图的最长路问题
答案:2 悬赏:30 手机版
解决时间 2021-01-04 09:59
- 提问者网友：遁入空寂
- 2021-01-04 05:31
最佳答案
- 五星知识达人网友：污到你湿
- 2021-01-04 06:49
用floyed算法
procedure floyed;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]>a[i,j] then a[i,j]:=a[i,k]+a[k,j];
end;
procedure floyed;
begin
for k:=1 to n do
for i:=1 to n do
for j:=1 to n do
if a[i,k]+a[j,k]>a[i,j] then a[i,j]:=a[i,k]+a[k,j];
end;
全部回答
- 1楼网友：末日狂欢
- 2021-01-04 08:23
你好！
楼上的很显然错了，最长路不具有最优子结构.
无向图的最长路问题恐怕是一个NPC
希望对你有所帮助，望采纳。
我要举报
如以上回答内容为低俗、色情、不良、暴力、侵权、涉及违法等信息，可以点下面链接进行举报！
点此我要举报以上问答信息
大家都在看
推荐资讯