Question

运筹学用dijkstra算法求最短路径

• 你的回答被采纳后将获得：
• 系统奖励15（财富值+成长值）+难题奖励10（财富值+成长值）+提问者悬赏40（财富值+成长值）

Answer 1

就是通过广度搜索遍历当前节点和子节点的关系，然后再依次递归。
我给你开个头啊:
首先设首节点为1,那么子节点是2,3,4,那么我分别遍历
1-2 = 4
1-3 = 5
1-4 = 2
全部遍历完后我在从下面的第一个子节点开始遍历,
1(-2)-5 = 11
1(-2)-3 = 10 和1-3 = 5 对比 5<10 那么 1-3 = 5

1(-3)-2 = 11 和1-2 = 4进行对比 4<11 那么1-2 = 4
1(-3)-6 = 14
1(-3)-4 = 6 和 1-4 = 2进行对比 2< 6 那么 1-4 =2

1(-4)-3 = 3 和 1-3=5 进行对比 5 > 3 那么 1-3 = 3
.......................
依次遍历完整个图

最开始设1 到其他点的路径为无限大，
然后依次遍历，if( ( 1到当前点的路径 + 当前点到某子节点的路径) < (1 到该子节点的路径) )
1到该子节点的路径 = 1到当前点的路径 + 当前点到该子节点的路径)