最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)简介Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。原理在已知图的邻接矩阵net.vexs[i][j](无向网,含权值的图)的条件下,通过遍历已知图的所有路径,用dis[i]数组来记录到i点…

大家好,又见面了,我是你们的朋友全栈君。

简介

     Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。由for循环可知,其时间复杂度是O(n^2)。

原理

      在已知图的邻接矩阵net.vexs[i][j](无向网,含权值的图)的条件下,过遍历已知图的所有路径,用dis[i]数组来记录到i点的最短路径,然后在循环中不断判断更替。首先,将所有点的集合分为俩部分,一边是已经遍历过的,另外一边是没有遍历过的,分别用mark[i]=1、mark[i]=0来表示。

代码通解

             在下面代码中,先将赋予初始值dis[i]=INF(无穷大)、mark[i]=0(未标记),而后单独将源点(x)所联通的路径权值net.arcs[x][i]赋予dis[i](<INF称为初始化),i为联通的点,暂定为到i的最短路径,标记mark[x]=1,即已经遍历;然后,在一个for遍历了所有节点的大循环里面:

                                                          ①寻找遍历到点联通路径(与之相连线的点)中权值最小的一条; 标记遍历点;

                                                          ②修正最短路径;

而后,便是已经遍历所有点了,dis[i]也在不断的修正中得到真正的最小值,即最短路径。详情看下列代码

#define MAXSIZE 20
#define PLACENUM 12
#define INF 9999           // 此处定义999为无穷大

struct
{
    int vexnum,arcnum;  //节点数和边数
    int vexs[MAXSIZE];      // 节点名
    int arcs[MAXSIZE][MAXSIZE];   //俩个节点之间的值
} net;
/*补充的结构体net,2019.7.3*/

void Dijkstra(int x,int y)      // x为源点,y为终点
{
    int i,j,k;
    int min;
    int u;   //下一个放入集合p的点
    int dis[net.vexnum];   //  最短路径
    int mark[net.vexnum];   //   被mark的便是已经遍历,未被mark的便是未遍历
    /*首先进行最短路径初始化*/
    for(i=0; i<net.vexnum; i++)
    {
        mark[i] = 0;
        dis[i] = net.arcs[x][i];
    }


    mark[x]=1;          // 标记源点
    
    
    for(k=0; k<net.vexnum; k++)          // for 大循环
    {
        min = INF;   //  min初始化最大值,便于后来数据替换(每一个点的出度入度判断)
        
        /*寻找遍历到点联通路径(与之相连线的点)中权值最小的一条; 标记遍历点;*/
        for(i=0; i<net.vexnum; i++)
        {
            if(mark[i]==0&&min>dis[i])      //判断未遍历点 且 被赋值的最短路径(dis[i]<INF),未被赋值的点     //                                                     应当min==dis[i]=INF
            {
               min = dis[i];             //在已知赋值最短路径中,寻找权值最小的点并将他作为下一个遍历 
               u=i;                            //点u点
            }
        }


        mark[u]=1;      //标记u点,下面u修正将会以最短路径进行辐射
 
        /*修正最短路径*/
        for(i=0;i<net.vexnum;i++)
        {
            if(!mark[i]&&dis[i]>dis[u]+net.arcs[u][i])                 // !mark[i]判断不去走回头路,         //                                                                                dis[i]>dis[u]+net.arcs[u][i]有俩个用途:①若u链接的是x源点没有赋值最短路径的点,那么这里可以赋值②若是赋值过的点,那么可以判断是上一个dis[i](此时是被赋值过的)是不是真正的最短路径,即修正。

            {
                dis[i] = dis[u] + net.arcs[u][i];      //若A->C比A->B->C更长那么A->B->C则是到C的最短路径,下图将解释。
         
                   }
             }
    }
     printf("最短路径值为:             %d",dis[y]);
}

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)我们以A,B,C三个点来举例子,三个点的最短路径分别为dis[0]、dis[1]、dis[2]。

                                                   ①A为源点初始化,dis[B]=3 (到B的最短路径,dis[1]),  dis[C]=6;

                                                   ②dis[B]<dis[C],选取B为u下一个遍历点;与B相联的有A(不走回头路)、E、C;

                                                   ③E未赋值,赋予dis[E];  C被之前赋予过,比较  dis[C] > dis[B] + net.arcs[B][C] (要不然你根本进不了这儿),重新赋值dis[C] = dis[B]+net.arcs[B][C];

                                                   ④大循环遍历所有点,走遍天下。

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

我觉得下面几张图很不错,图片取自https://www.cnblogs.com/biyeymyhjob/archive/2012/07/31/2615833.html

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

图一

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

图二

19.3.24

关于修正最短路径

请参考一下文中引入的动图(图一)和表格图(图二),迪杰斯特拉求最短路径是,将需要遍历的点集合一个个进行遍历的。!mark[i]是需要其值为false(尚未遍历到,这是相对于当前遍历点),当然,这就实现了它不会往回走,同时记录它“向前走”的最短距离点u,在其基础上(修正循环),与u点相连的未被标记(遍历到)的点记其中一个为z,判断源点x->z点们的dis(最短)值是否大于x->u->z点们的距离,如果大于,更新z点们的最新(新的路径)最短距离,在已知最短距离的情况下然后进行更新,直到遍历完所有的点集合(所有路径)。从源点往外辐射就能够理解了。

比如说1,2,3为三角形相互联系。当前是2。已经遍历了1,赋予了1->2、1->3、1->6的dis值,那么在修正部分就会从u(设12、13、16中12距离最小),也就是2往外与没遍历且相邻的3和4判断以下:1->3大于1->2->3?  1->4大于1->2->4?,如果大于,更新dis值,此为修正,这里在已知最短距离1->2的基础上修正了1->3和1->4的dis值。同理到3的时候会修正源点(x/1)到4和到6的最短距离。

下图圆形为已遍历点,方形为未遍历的集合数据,实线为相邻连线,虚线为修正过程。

PS:mark是已经被找过从该点出发的相邻路径,修正在已知最短距离的情况下(u),进行辐射,也就相对于找了u的所有相邻路径来比较更新(!mark[i]&& dis[i]>dis[u]+net.arcs[u][i]),但他并未记录u辐射的路径中的相邻最短路径(需要大循环)。

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)
遍历第一个点——1的过程
最短路径之Dijkstra(迪杰斯特拉)算法(无向图)
遍历点2的过程

21.4.16

关于负权值问题

迪杰斯特拉本质上是贪心:找局部最优解,前提是最终的结果是由不断简化问题的局部最优解组成的,贪心是一种特殊的动态规划:他只关注局部最优解(但是我们知道局部最优解不一定是全局最优)。弗洛伊德是动态规划。这里体现出一点:迪杰斯特拉只是单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。而弗洛伊德则是算出所有的点之间的最短路径(多对多)。

那么我们再看负权值问题:迪杰斯特拉:每次修正,我们只会修正当前点所连接的,未被遍历过的(mark[i]),注意前面这句话有两个条件。那么久说明他不会修改早已经(很久以前)就已经确定的最短路径,因为已经确定了是局部最优解,这里在代码里面也能看出来。而也因为这样,弗洛伊德是是能够算负权的(他可以更新“早已经”确定的最短路径,因为他要算出全部点之间的最短路径),值得注意的是弗洛伊德不能解决带有“负权回路”(或者叫“负权环”)的图,因为带有“负权回路”的图没有最短路。

除此之外,求带负权值边的单源最短路径还可以用贝尔曼-福特算法。至于迪杰斯特拉比弗洛伊德快,也是因为他是单源的缘故。

最短路径之Dijkstra(迪杰斯特拉)算法(无向图)

如果看懂了点个赞,给点小动力,谢谢啦~

PS:最简单(代码量)实现寻找最短路径的弗洛伊德算法点这里

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/136118.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • 大数据平台数据脱敏介绍

    大数据平台数据脱敏介绍数据脱敏(DataMasking),又称数据漂白、数据去隐私化或数据变形。百度百科对数据脱敏的定义为:指对某些敏感信息通过脱敏规则进行数据的变形,实现敏感隐私数据的可靠保护。这样,就可以在开发、测试和其它非生产环境以及外包环境中安全地使用脱敏后的真实数据集。可以看到数据脱敏具有几个关键点:敏感数据、脱敏规则、使用环境。敏感数据,又称隐私数据,常见的敏感数据有:姓名、身

  • UpdatePanel Control

    UpdatePanel Control原帖地址:http://www.cnblogs.com/caviare/archive/2007/09/21/901500.html另外关于UpdateProgress和Timer控件的使用,可以参考http://read.newbooks.com.cn/info/168590.html UpdatePanel  对于UpdatePanel控件的使用是ASP.N

  • win11安装node并且配置环境变量

    win11安装node并且配置环境变量npm使用过程中的一些错误解决办法及npm常用命令和技巧-世有因果知因求果-博客园用户名是自己的C:\Users\KenKen\AppData\Roaming\npmNODE_PATHC:\ProgramFiles\nodejs\node_modules

  • jquery checkbox 选中方法「建议收藏」

    jquery checkbox 选中方法「建议收藏」方法一:if($(“#checkbox-id”)get(0).checked){//dosomething}方法二:最佳if($(‘#checkbox-id’).is(‘:checked’)){//dosomething}方法三:if($(‘#checkbox-id’).attr(‘checked’)){//dos

  • myeclipse svn插件失效

    myeclipse svn插件失效最近经常遇到这个问题,在myeclipse2016上安装svn插件是将site目录copy到dropins目录下,可能这样做会导致以后安装其他新插件时,svn插件会失效,解决方案如下:找到myeclipse安装目录下的configuration目录下的org.eclipse.update包,然后把它删除,重启myeclipse,svn就会重新出现了!麻烦 …

  • Android studio 入门教程(案例)

    Android studio 入门教程(案例) 1.创建一个Android项目,点击File-&gt;New-&gt;NewProject,其中的open是打开一个Android项目2.输入项目的名称test,此项目放在E盘下,然后点击Finish3.选择Android虚拟机的版本,版本越低运行起来越快,其他的无需勾选。 4.选择Android的模板,选择基础类android的空模板Empty…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号