已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,
来源:学生作业帮助网 编辑:作业帮 时间:2024/06/30 03:19:06
![已知带权有向图如图7-29所示,请利用Dijkstra算法从顶点V4出发到其余顶点的最短路径及长度,](/uploads/image/z/5173946-26-6.jpg?t=%E5%B7%B2%E7%9F%A5%E5%B8%A6%E6%9D%83%E6%9C%89%E5%90%91%E5%9B%BE%E5%A6%82%E5%9B%BE7-29%E6%89%80%E7%A4%BA%2C%E8%AF%B7%E5%88%A9%E7%94%A8Dijkstra%E7%AE%97%E6%B3%95%E4%BB%8E%E9%A1%B6%E7%82%B9V4%E5%87%BA%E5%8F%91%E5%88%B0%E5%85%B6%E4%BD%99%E9%A1%B6%E7%82%B9%E7%9A%84%E6%9C%80%E7%9F%AD%E8%B7%AF%E5%BE%84%E5%8F%8A%E9%95%BF%E5%BA%A6%2C)
已知带权有向图如图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算法,图论中很重要的算法之一.