无向图求最短路径 |
您所在的位置:网站首页 › lingo求解最短路径无向图 › 无向图求最短路径 |
Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个顶点到其他所有顶点的最短路径。 问题描述: 如下无向图, 若从顶点1开始计算到其余各顶点的最短路径
首先需要3个辅助数组: dist[] : 记录从顶点1开始到其余各顶点的最短路径visited[] : 记录该顶点是否被访问过, 初始值设为0path[] : 记录该顶点最短路径的前驱顶点求最短路径步骤: ①初始化数组:计算从顶点0到其余各顶点的路径长度 顶点1234567dist[]012∞∞∞1614path[]-11-1-1-111visited[]1000000
②由于dist数组中目前最小值为顶点2,计算从顶点2到其余各顶点的距离, 若小于当前dist数组中的值, 则更新dist和path数组;若大于当前dist数组的值, 则不做改变 顶点1234567dist[]01222∞∞1614path[]-112-1-111visited[]1100000③选择dist数组中未被访问过的最小值顶点7, 同上 顶点1234567dist[]01222∞221614path[]-112-1711visited[]1100001
④选择dist数组中未被访问过的最小值顶点6 顶点1234567dist[]01222∞181614path[]-112-1611visited[]1100011
⑤选择dist数组中未被访问过的最小值顶点5 顶点1234567dist[]0122222181614path[]-1125611visited[]1100111
⑥选择dist数组中未被访问过的最小值顶点3或者4都可以, 如选择3 顶点1234567dist[]0122222181614path[]-1125611visited[]1110111⑦选择dist数组最后一个顶点4 顶点1234567dist[]0122222181614path[]-1125611visited[]1111111
到这里为止, visited数组元素全为1, 即所有顶点都被访问过, 最短路径见如上图。 |
今日新闻 |
点击排行 |
|
推荐新闻 |
图片新闻 |
|
专题文章 |
CopyRight 2018-2019 实验室设备网 版权所有 win10的实时保护怎么永久关闭 |