作业帮已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/08 09:19:21
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
初始化d[i]为无穷大,由于从v4开始,所以将d4=0,标记v4已选择.
下面开始Dijkstra算法：
和v4相连的且未标记的点有v2和v6,这样更新d2=20,d6=15,选择未标记所有点中最小的d6=15,标记v6已选择,这样我们算出了v4->v6最短距离d6=15；
从v6开始,和v6相连的且未标记的是v2,此时算d6+6=21>20,所以不更新d2,选择未标记所有点中最小的d2=20,标记v2已选择,这样算出了v4->v2最短距离d2=20；
从v2开始,和v2相连的且未标记的有v1和v5,d1=d2+10=30,d5=d2+30=50,选择未标记所有点中最小的d1=30,标记v1已选择,这样我们算出了v4->v1最短距离d1=30；
从v1开始,和v1相连的且未标记的有v3,d3=d1+15=45,选择剩下没被选的所有点的最小的d3=45(d5=50),标记v3已选择,这样我们算出了v4->v3最短距离d3=45
从v3开始,没有出去的路径,不更新距离,选择剩下没被选的所有点的最小的d5=50,标记v5已选择,这样我们算出了v4->v5最短距离d5=50.
此时所有的点都被访问,结束.
注：上面的标记点已选择注意下,在算法的实现中用的是将所有的点放入队列中,一旦一个点被选择就是说求出了最短距离,就从此队列删除该点,一直到此队列为空,结束算法,我写标记只是为了方便理解.
希望能帮你清晰了解Dijkstra算法,图论中很重要的算法之一.