像这种带权拓扑图应该怎样求最短路径? 2C

图片说明
如图,怎样求的从节点A到节点Y的最短路径?当然不能每步都选权值最小的,因为比如节点M就到不了节点Y嘛。那应该用什么方法呢?广度优先遍历?

2个回答

拓扑的话,应该能取到每个点的坐标X,Y,可以计算出没条线的长度,不就选出来了么。

这图没什么特别的,不可达的边(M到Y)可以把权设置为一个非常大的值(表示无穷大),图数据用一个二维数组表示就可以了
用常规的Dijkstra算法就可以解决了

Csdn user default icon
上传中...
上传图片
插入图片
抄袭、复制答案,以达到刷声望分或其他目的的行为,在CSDN问答是严格禁止的,一经发现立刻封号。是时候展现真正的技术了!