24小时热门版块排行榜    

北京石油化工学院2026年研究生招生接收调剂公告
查看: 1099  |  回复: 5
当前只显示满足指定条件的回帖,点击这里查看本话题的所有回帖

lw_9000

新虫 (初入文坛)

[求助] 求助通信网中一个和图论有关的题,用Dijkstra和Floyd算法,矩阵中有负值。

这个题让我很头痛,D算法不是不能用于有负值的么,求教大神解法。谢谢啦!

1111.jpg
回复此楼
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

chentianyu1

木虫 (小有名气)

【答案】应助回帖


感谢参与,应助指数 +1
lw_9000: 金币+1, ★★★很有帮助 2013-03-09 23:02:05
所有边加上最小的那个负数试试?
3楼2013-03-06 10:33:37
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
查看全部 6 个回答

iopiop007

金虫 (著名写手)

【答案】应助回帖

感谢参与,应助指数 +1
还有这规定,相当于负值的路径小于正值不就可以了?
2楼2013-03-06 00:19:54
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

comm_net

至尊木虫 (著名写手)

【答案】应助回帖

感谢参与,应助指数 +1
一般而言,用Dijkstra和Floyd算法要求距离值非负。对于你这种情况,可以尝试在所有边加上那个最小负数的绝对值,让后再所求的最短路径结果加上该最小负数。
4楼2013-03-08 17:23:11
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖

lw_9000

新虫 (初入文坛)

引用回帖:
4楼: Originally posted by comm_net at 2013-03-08 17:23:11
一般而言,用Dijkstra和Floyd算法要求距离值非负。对于你这种情况,可以尝试在所有边加上那个最小负数的绝对值,让后再所求的最短路径结果加上该最小负数。

您好,您的方法很不错。谢谢了哈。
5楼2013-03-09 23:02:44
已阅   回复此楼   关注TA 给TA发消息 送TA红花 TA的回帖
最具人气热帖推荐 [查看全部] 作者 回/看 最后发表
[考研] 085600材料与化工调剂 +10 kikiki7 2026-03-30 10/500 2026-03-30 21:37 by lixiang110
[考研] 367求调剂 +5 芋泥啵啵… 2026-03-28 5/250 2026-03-30 19:56 by 无际的草原
[考研] 一志愿:西北大学,英一数一408-284分求调剂 +5 12.27 2026-03-27 5/250 2026-03-30 19:31 by 源_2020
[考研] 化学0703 调剂 306分 一志愿211 +8 26要上岸 2026-03-28 8/400 2026-03-30 16:39 by herarysara
[考研] 生物技术与工程 +7 1294608413 2026-03-25 8/400 2026-03-30 11:36 by 唐沐儿
[考研] 348求调剂 +6 小懒虫不懒了 2026-03-28 6/300 2026-03-30 10:29 by Evan_Liu
[考研] 085404求调剂,总分309,本科经历较为丰富 +6 来财aa 2026-03-25 6/300 2026-03-30 09:48 by 青海小西牛
[考研] 311求调剂 +6 冬十三 2026-03-24 6/300 2026-03-29 20:45 by 无际的草原
[考研] 275求调剂 +15 Micky11223 2026-03-25 20/1000 2026-03-29 20:44 by 唐沐儿
[考研] 294分080500材料科学与工程求调剂 +8 柳溪边 2026-03-26 8/400 2026-03-29 20:42 by 唐沐儿
[考研] 0856求调剂 +13 zhn03 2026-03-25 14/700 2026-03-29 08:13 by fmesaito
[考研] 330分求调剂 +5 qzenlc 2026-03-29 5/250 2026-03-29 07:37 by 无际的草原
[考研] 11408软件工程求调剂 +3 Qiu学ing 2026-03-28 3/150 2026-03-28 21:50 by zhq0425
[考研] 本科新能源科学与工程,一志愿华理能动285求调剂 +7 AZMK 2026-03-28 11/550 2026-03-28 21:01 by xxxsssccc
[考研] 266分,求材料冶金能源化工等调剂 +7 哇呼哼呼哼 2026-03-27 9/450 2026-03-28 12:22 by zllcz
[考研] 286求调剂 +12 PolarBear11 2026-03-26 12/600 2026-03-28 12:14 by zllcz
[考研] 药学105500求调剂 +3 Ssun。。 2026-03-28 3/150 2026-03-28 11:24 by lxf170613
[考博] 26申博 +3 加油冲啊! 2026-03-26 3/150 2026-03-27 15:38 by cls512
[考研] 308求调剂 +7 墨墨漠 2026-03-25 7/350 2026-03-27 14:47 by 狂炫麦当当
[考研] 材料考研调剂生 +3 黄粱一梦千年 2026-03-24 3/150 2026-03-24 17:00 by barlinike
信息提示
请填处理意见