精华内容
下载资源
问答
  • 复习了迪杰斯特拉算法,在这里写一个小例子,供大家参考,例子主要是知道起点的情况下,求一个图中到各个点的最短路径。 这是一开始给的图,假设我们从A出发,寻找从A分别到B,C,D,E,F的最短路径,过程如下: 1,...

    复习了迪杰斯特拉算法,在这里写一个小例子,供大家参考,例子主要是知道起点的情况下,求一个图中到各个点的最短路径。


    这是一开始给的图,假设我们从A出发,寻找从A分别到B,C,D,E,F的最短路径,过程如下:

    1,对于A,A->A=0,这就是最短路径;


    2,对于A,我们继续向下索引,有A->B=6,A->C=3,A->other=∞,所以我们选择A->C作为第二个路径;


    3,对于A->C,我们可以继续向下索引,这个时候会有A->C->B=5,A->C->D=6,A->C->E=7,A->C->F=∞,所以我们选择A->C->B=5作为第三个路径;


    4,对于A->C->B,我们继续向下索引,可以得到A->C->B->D=11,A->C->B->F=∞,这个时候到了关键的地方,因为对于A->D,我们之前已经得到过从A走到D的路径相比于现在有更加优秀的A->C->D=6,所以舍弃这一步的A->C->B->D=11,而是选择A->C->D为第四个路径;


    5,对于A->C->D,我们可以得到A->C->D->E=8,A->C->D->F=9,同上,这个时候我们有A->C->E=7,所以舍弃A->C->D->E=8,将A->C->E作为第五个路径;


    6,对于A->C->E,我们可以求出A->C->E->F=12,这个时候又是同上,有A->C->D->F=9,所以舍弃这一步求出来的值,得到A->C->D->F=9,至此,求最短路径已经全部完毕。


    7,结论是:

    A->A = 0;

    A->B = A->C->B = 5;

    A->C = 3;

    A->D = A->C->D=6;

    A->E = A->C->E=7;

    A->F = A->C->D->F=9.


    展开全文
  • Dijkstra算法(迪杰斯特拉算法) 本文主要介绍Dijkstra算法(迪杰斯特拉算法)的思想没有源码实现,但写出了思路流程。当你了解这个算法思想后会很容易写出源码。Dijkstra算法(迪杰斯特拉算法)是比较常用的最短路径算法...

    Dijkstra算法(迪杰斯特拉算法)

    本文主要介绍Dijkstra算法(迪杰斯特拉算法)的思想没有源码实现,但写出了思路流程。当你了解这个算法思想后会很容易写出源码。Dijkstra算法(迪杰斯特拉算法)是比较常用的最短路径算法,可以算是贪心思想的实现。贪心思想是在对问题求解时,总是做出在当前看来是最好的选择。
    Dijkstra算法核心就是求出局部最优解。下面用open,close表描述Dijkstra算法的过程。
    首先介绍下open表和close表,open表用于存储未探索的节点,也可以理解为这次探索到的新节点。close表用于存储已经探索过的节点(当前最优路线)。
    在这里插入图片描述

    初始化将起点分别放入open表和close表中。open表是一个优先队列(用set实现元素结构为坐标和距离起点的长度)每次弹出最小值。close表是一个map(key为当前节点下标,value元素为结构为前一节点下标和距离起点长度)通过当前坐标寻找前指针和当前坐标距离起点的长度。循环步骤如下:1.2
    1.从open表中弹出距离起点最近的节点,判断下探索到的节点是否为终点(每次弹出的都是最优路线),探索该节点的相邻节点。
    这里说明下为什么open表弹出来的就是最优路线,弹出的节点到达起点的路径已经是最短路径,经过其他大于该节点的节点到达该节点,距离一定大于此次弹出的这个距离。
    2.探索到的相邻节点先到close表中去查找是否被探索过,如果被探索过就比较距离,如果此次距离小于close表中存储的距离那么就更新close表(更新前指针和距离)和open表(更新距离),此次距离不小于close表中存储的距离就可以忽略本次;如果close表中不存在该节点那么直接插入到close表中,并插入open表中。
    这里说明下为什么更新open表,因为close表中出现了该节点被探索过所以open表中一定存在距离起点长度大于此次探索到的节点距离起点的长度,open每次是弹出距离起点最短的节点,如果不更新就会导致节点弹出顺序错误。
    初始化:
    open表:起点坐标为0,距离起点距离为0,此时该set中只有一个元素
    在这里插入图片描述
    close表:起点的坐标为0,距离起点距离为0
    在这里插入图片描述
    第一次循环:
    弹出open首节点(set自动排序最小值在最前面)
    找到相邻节点为1,2节点,到close表中查找1,2节点是否存在,不存在直接插入表close,同时插入open表
    第一次循环
    第二次循环:
    继续弹出open首节点1
    找到相邻节点2,3节点,到close表中查找2,3节点是否存在,2节点存在则比较距离
    (0->1->2=10)<(0->2=12)所以更新close中2节点,3节点不存在直接插入close,同时更新open表中2节点和插入3节点
    第二次循环第三次循环:
    继续弹出open首节点3
    找到相邻节点2,4,5节点,到close表中查找2,4,5节点是否存在,2节点存在则比较距离
    (0->1->3->2=8)<(0->1->2=10)所以更新close中3节点,4,5节点不存在直接插入close,同时更新open表中2节点和插入4,5节点
    第三次循环
    第四次循环:
    继续弹出open首节点2
    找到相邻节点4节点,到close表中查找4节点是否存在,4节点存在则比较距离
    (0->1->3->2->4=13)<(0->1->3->4=17)更新open和close
    第四次循环
    第五次循环:
    继续弹出open首节点4
    找到相邻节点5节点,到close表中查找5节点是否存在,5节点存在则比较距离
    (0->1->3->2->4->5=17)=(0->1->3->5=19)更新close更新open 第五次循环
    6.弹出顶点判断顶点为终点结束循环

    总结

    Dijkstra算法利用优先队列可以自己排序的优势每次弹出的都是当前最优路径和上一篇写过的广度优先算法对比优势一目了然。
    广度优先算法链接:https://blog.csdn.net/qq_33865609/article/details/117062138
    以上文章作者通过上网查找资料自己思考总结而来,如有不足,不吝赐教,谢谢。

    展开全文
  • 今天我们来了解一下十分常用的迪杰斯特拉算法。 2.dj是一种求非负权值的单源最短路算法。通俗的讲就是求这样的问题:在图中的两个点s,t并且这个图中没有负的边权,那么求解从s到t的最短的路径权值和是多少。首先...

    1.图中的最短路径求解的算法花样百出,但是最常用的就是那几种很耳熟能详的算法。今天我们来了解一下十分常用的迪杰斯特拉算法。

    2.dj是一种求非负权值的单源最短路算法。通俗的讲就是求这样的问题:在图中的两个点s,t并且这个图中没有负的边权,那么求解从s到t的最短的路径权值和是多少。首先说明几个特点,注意dj的使用范围,非负权值的单源最短路。但是虽然我们求的是s到t的最短路,但是求解过程中会把s到图中所有点的最短路都求出来。这是dj的一些特性,为什么会有这样的特性,我们来看一下原理就明白了。

    3.dj算法的原理:首先看图

                                                        

    假设我们要求0到4的最短路,那么其实dj是这样运行的,它的基本思想就是贪心和松弛。他首先把点分为两个集合s和t,s代表已经求得的最短路径的点,t代表还未求得最短路的点。初始位置s里面只有源点,也就是0其他节点都在t里。然后会有一个dis数组,保存当前状态下源点到各个节点的最短路,dis初始化的结果就是源点到各个点之间的路径长度,如果有直接的连边,就是这个连边的长度,如果没有就是INF,例如上图中我们可以知道dis[1]=10,dis[4]=100,dis[2]=inf。然后就可以开始工作了。工作的流程是这样的,首先我们从源点出发,找到距离最近的点(贪心),没错,我们在这个图中找到的就是10,找到之后更新dis对应的值(当然这里的更新是没有意义的,因为是一样的),然后我们松弛这是很重要的,或者说这就是dj的精髓。怎么松弛呢?是这样工作的,我们现在已经有了1点,1被加入s集合中,我们通过1可以到达2,并且路径的长度是50,所以0到达2的路径长度就是60,因为之前0到2是没有直接的路径的,所以我们这个时候就可以把路径更新到60,这样就完成了松弛。当然了,dj并不仅仅是这么运作的,当找到1之后,他会计算发现到2的长度是60,但是到3的长度是30(这里的到指的是源点到其他点),所以他会选择小的去,所以第二个被加入的节点是3而不是2(这也是一种贪心的策略)。然后这个时候我们依然使用上边的方法,我们发现这个时候可以到达的点有2,4,但是到达4的最短路径是90,到达2的是50(通过3来松弛),这个时候2倍加入s集合,2被加入s集合之后,我们又可以通过2来松弛4,所以到4的最短路径就是60了。这样所有点被加入集合。最短路算法完成。

    4.疑惑的解决:开始的时候我们就提出了两个问题。1.dj是基与非负权值的。2.dj虽然是求两个点之间的最短路,但是会把源点到其他所有点的最短路都求出来。现在看完原理之后我想就很好回答这个问题了,首先为什么是非负权值,因为dj的松弛过程决定的,如果出现负边,那么松弛的时候就会在哪个具有负边的地方循环。其次,虽然是求两点之间的最短路,但是任何一点的加入都有可能会对这两点之间的最短路产生松弛。所以我们需要把所有的点都加进去试一遍。

    5.dj的复杂度是n方的,这个与图是怎么存的没有关系。下面给出实现的代码:

    /*Dijkstra求单源最短路径 */
     
    #include <iostream>
    #include<stack>
    #define M 100
    #define N 100
    using namespace std;
    
    typedef struct node
    {
        int matrix[N][M];      //邻接矩阵 
        int n;                 //顶点数 
        int e;                 //边数 
    }MGraph; 
    
    void DijkstraPath(MGraph g,int *dist,int *path,int v0)   //v0表示源顶点 
    {
        int i,j,k;
        bool *visited=(bool *)malloc(sizeof(bool)*g.n);
        for(i=0;i<g.n;i++)     //初始化 
        {
            if(g.matrix[v0][i]>0&&i!=v0)
            {
                dist[i]=g.matrix[v0][i];
                path[i]=v0;     //path记录最短路径上从v0到i的前一个顶点 
            }
            else
            {
                dist[i]=INT_MAX;    //若i不与v0直接相邻,则权值置为无穷大 
                path[i]=-1;
            }
            visited[i]=false;
            path[v0]=v0;
            dist[v0]=0;
        }
        visited[v0]=true;
        for(i=1;i<g.n;i++)     //循环扩展n-1次 
        {
            int min=INT_MAX;
            int u;
            for(j=0;j<g.n;j++)    //寻找未被扩展的权值最小的顶点 
            {
                if(visited[j]==false&&dist[j]<min)
                {
                    min=dist[j];
                    u=j;        
                }
            } 
            visited[u]=true;
            for(k=0;k<g.n;k++)   //更新dist数组的值和路径的值 
            {
                if(visited[k]==false&&g.matrix[u][k]>0&&min+g.matrix[u][k]<dist[k])
                {
                    dist[k]=min+g.matrix[u][k];
                    path[k]=u; 
                }
            }        
        }    
    }
    
    void showPath(int *path,int v,int v0)   //打印最短路径上的各个顶点 
    {
        stack<int> s;
        int u=v;
        while(v!=v0)
        {
            s.push(v);
            v=path[v];
        }
        s.push(v);
        while(!s.empty())
        {
            cout<<s.top()<<" ";
            s.pop();
        }
    } 
    
    int main(int argc, char *argv[])
    {
        int n,e;     //表示输入的顶点数和边数 
        while(cin>>n>>e&&e!=0)
        {
            int i,j;
            int s,t,w;      //表示存在一条边s->t,权值为w
            MGraph g;
            int v0;
            int *dist=(int *)malloc(sizeof(int)*n);
            int *path=(int *)malloc(sizeof(int)*n);
            for(i=0;i<N;i++)
                for(j=0;j<M;j++)
                    g.matrix[i][j]=0;
            g.n=n;
            g.e=e;
            for(i=0;i<e;i++)
            {
                cin>>s>>t>>w;
                g.matrix[s][t]=w;
            }
            cin>>v0;        //输入源顶点 
            DijkstraPath(g,dist,path,v0);
            for(i=0;i<n;i++)
            {
                if(i!=v0)
                {
                    showPath(path,i,v0);
                    cout<<dist[i]<<endl;
                }
            }
        }
        return 0;
    }

     

     

     

    展开全文
  • 最短路径算法在生活中有极其重要的意义与运用,如高铁、地铁的路线规划问题,最近学习了迪杰斯特拉算法,颇有感慨,遂成一篇笔记以记之。 以邻接矩阵为存储结构,如下图所示: 拓扑结构图如下: 求v0到v8的最短路径...

    最短路径算法在生活中有极其重要的意义与运用,如高铁、地铁的路线规划问题,最近学习了迪杰斯特拉算法,颇有感慨,遂成一篇笔记以记之。
    以邻接矩阵为存储结构,如下图所示:
    在这里插入图片描述
    拓扑结构图如下:在这里插入图片描述

    求v0到v8的最短路径,其实思想比较简单,蕴含着贪心法的思想,它并不是一下子求出v0到v8的最短路径,而是先求出v0到v1的最短路径,再求出v2到v3的最短路径,过程就是基于已经求出的最短路径的基础上,求出更远拓扑点的最短路径,最终得出结果;

    初始时d,p,final数组的值如下:
    d: 0 1 5 65535 65535 65535 65535 65535 65535
    p: 0 0 0 0 0 0 0 0 0
    final: 1 0 0 0 0 0 0 0 0

    代码如下:

    #define MAXVEX 9
    #define INFINITY 65535 //定义两个宏,主要是便于以后修改数据
    
    typedef int Patharc[MAXVEX];//用于存储最短路径下标的数组
    typedef int ShortPathTable[MAXVEX];//用于存储到各点的最短路径权值之和 
    
    void shortpath_dj(Mgraph g,int v0,Patharc *p,ShortPathTable *d)
    {
      int v,w,k,min;
      int final[MAXVEX];//final[w]表示已经求得顶点V0到Vw的最短路径,其实就是一个标记数组;
      
    //初始化数据
    for(v=0;v<.num;v++)
      {
        final[v]=0;  //全部顶点初始化为未找到最短路径;
        (*d)[v]=g.arc[v0][v];  //将和v0点有连线的顶点加上权值;这时初始化完成之后*d指向的数组内容即为邻接表的第一行内容,图中的无穷大全部用65535替代;
        (*p)[v]=0;    //初始化路径数组p为0;
      }
      (*d)[v0]=0;  //v0到v0的的路径为0;
      final[v0]=1; //v0到v0不需要求路径;
    
    //开始主循环,每次求出v0到某一个顶点的最短路径;
    for(v=1;v<g.num;v++)
      {
        min=INFINITY;
        for(w=0;w<g.num;w++)
          {
            if(!final[w]&&(*d)[w]<min)
              {
                k=w;
                min=(*d)[w];
              }
          }
          final[k]=1; //表示目前找到的最近顶点下标所对应的内容置1,即代表找到了v0到该点的最短路径;
     }
    
    //修正当前的最短路径以及距离;
    for(w=0;w<g.num;w++)
      {
        //如果经过v顶点的路径比现在这条路径的长度短时,就将其覆盖;
        if(!final[w]&&(min+g.arc[k][w]<(*d)[w]))
          {
            (*d)[w]=min+g.arc[k][w];  //修改当前路径的长度,其实(*d)就是一个临时数组,用来不断去更好地取值,这也是贪心法的表现,也可以说这个数组喜新厌旧哈;
            (*p)[w]=k;   //*p你也可以理解为是用来存放前驱结点的数组,具有双重含义,就像现实生活中人们说话有时也有两层意思差不多。比如(*p)[2]内容为1,就表示v2顶点的前驱是v1!
          }
      }
    
    
    }

    每次循环之后,三个数组的值都会相应的变化,最终d,p,final三个辅助数组的值如下,大家可以顺着程序推演一下,很容易就可以推出,也将很好的理解dj算法原理:
    d: 0 1 4 7 5 8 10 12 16
    p: 0 0 1 4 2 4 3 6 7
    final: 1 1 1 1 1 1 1 1 1

    看似复杂的算法也就是通过一步步的组合而成,仔细分析就可得其精髓。

    展开全文
  • 过程 首先需要记录每个点到原点的距离,这个距离会在每一轮遍历的过程中刷新。每一个节点到原点的最短路径是其上一个节点(前驱节点)到原点的最短路径加上前驱节点到该节点的距离。以这个原则,经...
  • 迪杰斯特拉算法:按路径长度递增的次序产生最短路径的算法。 问题描述:给定带权有向图G和原点v0,求从v0到G其余各顶点的最短路径。   求解过程: 对于网N=(V,E),将N中顶点分成两组: 第一组S :已求出的...
  • Dijkstra算法是按照路径长度递增的方法计算某一点到其余各顶点的最短路径。其算法的基本思想是:把图中所有顶点分成两组,第一组包括已确定最短路径的...在这个过程中,总保持v0到第一组各顶点的最短路径都不大于从v...
  • 迪杰斯特拉(Dijkstra)算法最通俗易懂的讲解

    万次阅读 多人点赞 2019-03-21 11:19:57
    划重点,迪杰斯特拉最最朴素的思想就是按长度递增的次序产生最短路径。即每次对所有可见点的路径长度进行排序后,选择一条最短的路径,这条路径就是对应顶点到源点的最短路径。 Tips:可见点就是从源点开始按广度...
  • CSP-迪杰斯特拉算法和变形求解最短路问题 文章目录CSP-迪杰斯特拉算法和变形求解最短路问题知识简述题目概述INPUT&输入样例OUTPUT&输出样例题目重述思路概述(分层Dij或枚举变式)题目源码(C++) 知识简述 ...
  • 图论--最短路径

    2018-08-03 10:32:47
    1.迪杰斯特拉算法求解过程: //V 为顶点的有穷非空集合,E为V中顶点偶对的有穷集合,这些顶点的偶对称为边,即E为边的集合。 对于网 N=(V,E),将N中的定点分成两组: 第一组S:已求出最短路...
  • 关于迪杰斯特拉算法→最短路径 两算法的区别: 弗洛伊德算法是可以解决任意两点间的最短路径的一种算法 Dijkstra算法是用于求解图中某源点到其余各顶点的最短路径的算法 那我们来看看弗洛伊德算法 思想 通过Floyd计算...
  • 图的应用的几种算法

    2021-05-08 19:23:43
    算法实现Dijkstra算法(迪杰斯特拉算法)1.求解过程2.算法实现Floyd算法(弗洛伊德算法)1. 算法过程2.算法实现 在介绍这些算法之前先介绍什么是最小生成树,在一个连通网的所有生成树中,各边的代价之和最小的那棵树...
  • 搜索最优解算法之贪心算法

    万次阅读 2016-05-03 21:21:21
    迪杰斯特拉算法是贪心算法的一个典型案例。 贪心算法不是对所有问题都能得到整体最优解,关键是贪心策略的选择,选择的贪心策略必须具备无后效性,即某个状态以前的过程不会影响以后的状态,只与当前状态有关。[1...
  • 虽然能用迪杰斯特拉算法求出图中某一个顶点到其余各个顶点的最短路径,但是如果求图中任意一对顶点间的最短路径,通常用弗洛伊德算法求解。【弗洛伊德算法求解最短路径的一般过程】、 第一步,这是两个矩阵A和Path...
  • 算法设计策略

    2019-08-05 18:52:22
    一、算法分析技术 循环 斐波那契算法 ...迪杰斯特拉和克鲁斯卡尔算法都是贪心法。 贪心法具有以下特点: 多阶段决策(解决问题的过程可以分为若干阶段) 无后向性(每一阶段面临的子问题只与当前阶...
  • (2)掌握求解单源点最短路径的迪杰斯特拉(Dijkstra)算法; (3)掌握拓扑排序的方法; (4)理解上述算法的程序实现。 二、实验环境 Windows 7以上版本的操作系统,Visual Studio 2010以上环境。 三、实验内容 1.请...
  • 迪杰斯特拉Dijkstra算法: 该算法用来求解从某个源点到其余各顶点的最短路径 以该图为例: 其邻接矩阵为: 最短路径为: 具体过程算法中用到了三个辅组数组: S[i]:布尔值记录到顶点最短路径是否已经被确定 ...
  • 建立静止节点的权重图,并利用迪杰斯特拉算法(Dijkstra)寻找所需最少数目的移动节点和构建栅栏覆盖的最短路径.根据构建栅栏覆盖的最短路径和基于路径上的每个栅栏漏洞所需的最少移动节点,将栅栏漏洞划分为简单情况和...
  • 每日Scrum(8)

    2019-10-02 13:06:32
    (1)在图的设计过程中掌握了图的基本运算函数...(2)在迪杰斯特拉算法的基础上实现任意两点间的最短路径的求法和顺序路径的问题。 任务展板 燃尽图 转载于:https://www.cnblogs.com/TDGA/p/5436178.html...
  • 【PAT1003】-Emergency

    2021-03-04 16:10:13
    PAT甲组1003.Emergency (优先队列实现迪杰斯特拉算法,Bellman算法,SPFA)思路与注意点–补充《算法笔记》 重要警示!!! 不要再脑子不清楚的情况下瞎做题,我一直认为自己的思路没有问题,原来是我没注意题目想要...
  • 【每日scrum】NO.8

    2015-05-13 08:09:00
    (1)在图的设计过程中掌握了图的基本运算函数的算法的理解和...(2)在迪杰斯特拉算法的基础上实现任意两点间的最短路径的求法和顺序路径的问题。 转载于:https://www.cnblogs.com/wurenxing/p/4499284.html...
  • 每日Scrum--No.8

    2016-04-26 18:46:00
    Problem:在图的设计过程中掌握了图的基本运算函数的算法的理解和程序的有效吸收,包括图的深度和广度优先的遍历,对图的联通分量的求解,图的最小生成树,图的拓扑排序,图的关键路径,以及在迪杰斯特拉算法的基础上...
  • Dijkstra原理及java实现

    2017-03-29 12:20:02
    二华为2017春招题一、Dijkstra原理简介Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法,用于计算一个节点到其他所有节点的最短路径。其基本思想是,设置顶点集合S并不断地作贪心选择来扩充这个集合。一个顶点...
  • 最短路径2.1从某个源点到其余各顶点的最短路径Dijkstra(迪杰斯特拉)2.2每一对顶点之间的最短路径(Floyd)3.拓扑排序3.1AOV--网3.1.1AOV--网的定义3.2拓扑排序的过程3.3检测AOV网中是否存在环的方法4.关键路径4.1...

空空如也

空空如也

1 2
收藏数 27
精华内容 10
关键字:

迪杰斯特拉算法求解过程