温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

Dijkstra算法举例分析

发布时间:2021-12-08 14:02:00 来源:亿速云 阅读:256 作者:iii 栏目:大数据

本篇内容主要讲解“Dijkstra算法举例分析”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Dijkstra算法举例分析”吧!

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。
最短路径?其实就是字面意思,一个带边值的图中从某一个顶点到另外一个顶点的最短路径。
官方定义:对于内网图而言,最短路径是指两顶点之间经过的边上权值之和最小的路径。
并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。
由于非内网图没有边上的权值,所谓的最短路径其实是指两顶点之间经过的边数最少的路径。

它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。

迪杰斯特拉算法时间复杂度为 0(n^2);

算法在实现步骤上类似与 普利姆算法  从最原始顶点开始 一步一步求到所有顶点的最小距离;

但是如果我们要寻找另外一个点到所有点的距离最小值 就要重新运行一遍这个算法

#define maxV 9 //最大顶点数  
#define min 65535;  
void DJSTL(MGraph G, int pos) //pos 这点到其余个点距离最小值  
{  
    bool final[maxV];//判断是否已经存到S集合中  
    int ShortPath[maxV];//一个点到其余点的距离 存储的是长度  
    int PathArc[maxV];// 存储最短路径下标  
    for(int i = 0; i<G.numV; i++)  
    {  
        ShortPath[i] = G.arr[pos][i];  
        final[i] = false;  
        PathArc[i] = 0;  
    }  
    ShortPath[pos] = 0; //该点到自身距离  
    final[pos] = true; //将该店纳入 final 集合中  
    //开始主循环每次求的pos这点要某个顶点的最短路径  
    int k=0;  
    for(int v=1;v<G.numV; v++)  
    {  
        int min = 65535;  
  
        for(int w=0;w<G.numV;w++)  
        {  
            if(!final(w) && ShortPath[w]<min)  
            {//不是到本身的最短的一个点的距离,类似普里姆法  
                min = ShortPath[w];  
                k = w;  
            }  
        }  
        final[k] = true ;//将该点纳入final数组中  
        for(int j=0;j<G.numV;j++)  
        {  
            if(!final[j] && (min+G.arr[k][j])<ShortPath[j])  
            {  
                ShortPath[j] = min+G.arr[k][j];  
                PathArc[j] = k;  
            }  
        }  
    }  
}

比如pos=0时求的 ShortPath{0,1,4,7,5,8,10,12,16}他表示V0 这个点到各个顶点的最短路径数。比如V0->V8 = 16 V0->V7=12;

PathArc{0,0,1,4,2,4,3,6,7}   

PathArc[8]=7 表示V0->V8 终点V8的前驱顶点是V7 

PathArc[7]=6 表示V7前驱顶点是V6

PathArc[6]=3 表示V6前驱顶点是V3

PathArc[3]=4 表示V3前驱顶点是V4

PathArc[4]=2 表示V4前驱顶点是V2

PathArc[2]=1 表示V2前驱顶点是V1

PathArc[1]=0 表示V1前驱顶点是V0

最短路径为V0->V1->V2->V4->V3->V6->V7->V8

到此,相信大家对“Dijkstra算法举例分析”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI