专栏首页图灵技术域迪杰斯特拉算法原理Dijkstra

迪杰斯特拉算法原理Dijkstra

1.定义概览

Dijkstra(迪杰斯特拉)算法是典型的单源最短路径算法,用于计算一个节点到其他所有节点的最短路径。主要特点是以起始点为中心向外层层扩展,直到扩展到终点为止。Dijkstra算法是很有代表性的最短路径算法,在很多专业课程中都作为基本内容有详细的介绍,如数据结构,图论,运筹学等等。注意该算法要求图中不存在负权边。

问题描述:在无向图 G=(V,E) 中,假设每条边 E[i] 的长度为 w[i],找到由顶点 V0 到其余各点的最短路径。(单源最短路径)

2.算法描述

1)算法思想:设G=(V,E)是一个带权有向图,把图中顶点集合V分成两组,第一组为已求出最短路径的顶点集合(用S表示,初始时S中只有一个源点,以后每求得一条最短路径 , 就将加入到集合S中,直到全部顶点都加入到S中,算法就结束了),第二组为其余未确定最短路径的顶点集合(用U表示),按最短路径长度的递增次序依次把第二组的顶点加入S中。在加入的过程中,总保持从源点v到S中各顶点的最短路径长度不大于从源点v到U中任何顶点的最短路径长度。此外,每个顶点对应一个距离,S中的顶点的距离就是从v到此顶点的最短路径长度,U中的顶点的距离,是从v到此顶点只包括S中的顶点为中间顶点的当前最短路径长度。

2)算法步骤:

a.初始时,S只包含源点,即S={v},v的距离为0。U包含除v外的其他顶点,即:U={其余顶点},若v与U中顶点u有边,则<u,v>正常有权值,若u不是v的出边邻接点,则<u,v>权值为∞。

b.从U中选取一个距离v最小的顶点k,把k,加入S中(该选定的距离就是v到k的最短路径长度)。

c.以k为新考虑的中间点,修改U中各顶点的距离;若从源点v到顶点u的距离(经过顶点k)比原来距离(不经过顶点k)短,则修改顶点u的距离值,修改后的距离值的顶点k的距离加上边上的权。

d.重复步骤b和c直到所有顶点都包含在S中。

C++

#define MAXVEX  9  
#define INFINITY    65536  
int Patharc[MAXVEX];//用于存储最短路径下标的数组  
int ShortPathTable[MAXVEX];//用于存储到各点最短路径的权值和  
  
void ShortTestPath_Dijkstra(MGraph G,int V0,Patharc *p,ShortPathTable *D){  
    //G顶点的矩形举证,V0 表示起始的顶点,p=Patharc,D=ShortPathTable  
    int v,w,k,min;  
    int final[MAXVEX];//final[w] =1 表示已经求得顶点V0到VW的最短路径  
      
    //初始化路径  
    for(v=0;v<G.numVertexes;v++){  
        final[v]=0;//全部顶点初始化为未找到的最短路径  
        (*D)[v]=G.arc[V0][v];//将于V0点有连线的顶点加上权值  
        (*P)[v]=0;//初始化路径数组P为0  
    }  
    (*D)[V0]=0;//V0 到V0的路径为0  
    final[V0]=1;//V0 到V0不需要求路径  
    //开始主循环,每次求得到V0到某个V顶点的最短路径  
    for(v=1;v<G.numVertexes;v++){  
        min=INFINITY;  
        for(w=0;w<G.numVertexes;w++){  
            if(!final[w] && (*D)[w]<min){  
                k=w;//获取最小的路径  
                min=(*D)[w];  
            }  
        }  
        final[k]=1;//将目前找到的最近顶点设1  
        //修正当前最短路径及距离  
        for(w=0;w<G.numVertexes;w++){  
            //如果经过v顶点的路径比现在这条路径的长度短的话,更新!  
            if(!final[w] && (min+G.arc[k][w] < (*D)[w])){  
                (*D)[w]=min+G.arc[k][w];//修改当前路径长度  
                (*p)[w]=k;//存放前驱顶点  
            }  
        }  
    }  
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

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

    2.执行上述 4、5两步骤,找出U集合中路径最短的节点D 加入S集合,并根据条件 if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B...

    狼啸风云
  • 一步一步深入理解Dijkstra算法

    先简单介绍一下最短路径: 最短路径是啥?就是一个带边值的图中从某一个顶点到另外一个顶点的最短路径。 官方定义:对于内网图而言,最短路径是指两顶点之间经过的边...

    Angel_Kitty
  • 迪杰斯特拉算法

    2.首先要有两个数组 一个用于存储两点间的距离(边),另一个数组用于存放当前点的前一个点 parent

    圆号本昊
  • 算法:最短路径之迪杰斯特拉(Dijkstra)算法

    对于网图来说,最短路径,是指两顶点之间经过的边上权值之和最少的路径,并且我们称路径上的第一个顶点为源点,最后一个顶点为终点。最短路径的算法主要有迪杰斯特拉(Di...

    s1mba
  • 最短路径—弄懂Dijkstra(迪杰斯特拉)算法

    对于 dijkstra算法,很多人可能感觉熟悉而又陌生,可能大部分人比较了解 bfs和dfs,而对dijkstra和floyd算法可能知道大概是图论中的某个算法...

    bigsai
  • 最短路径问题--迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型的用来解决最短路径的算法,也是很多教程中的范例,由荷兰计算机科学家狄克斯特拉于1959年提出,用来求从起始点到其他所有点...

    用户6021899
  • 单源最短路径之迪杰斯特拉算法

    迪杰斯特拉(Dijkstra)算法解决最短路径问题,其创造者:艾兹格·W·迪科斯彻 (Edsger Wybe Dijkstra)。

    每天学Java
  • 迪杰斯特拉(Dijkstra)算法求图中最短路径

    迪杰斯特拉(Dijkstra )算法: 对于图G=(V,E),将图的顶点分为两组: 顶点集S:已求出的最短路径的顶点集合(初始为{v0}); 顶...

    Steve Wang
  • 【你该懂一点Javascript算法系列】之单源最短路径 - Dijkstra算法

    ps: 邻接矩阵的意思是: 用一个二数组表示个顶点间的关系,来确定各顶点间的关系,因为图为有向图,所以上图的邻接矩阵如上

    super.x
  • 迪杰斯特拉(dijkstra)c语言实现方法

    迪杰斯特拉(dijkstra)是用来实现查找一个点到其它点最短路径的一种方法。通过查找从起点到最短距离的点,然后将该点放入到集合中,代表以及找到起点到这一点的最...

    诸葛青云
  • [图]最短路径-Dijkstra算法

    2.BFS可能会是Dijkstra算法的实质,BFS使用的是队列进行操作,而Dijkstra采用的是优先队列。

    王荣胜
  • 贪心算法(五)——迪杰斯特拉算法

    问题描述 给一个有向无环带权图,并给一个起点,求出该原点到所有顶点的最短路径。 ? 数据结构 dis: Map<String,Integer> dis; ...

    大闲人柴毛毛
  • 最短路径-----迪杰特斯拉算法

    大忽悠爱学习
  • 数据结构与算法——图最短路径

    最短路径问题一直是图论研究的热点问题。例如在实际生活中的路径规划、地图导航等领域有重要的应用。关于求解图的最短路径方法也层出不穷,本篇文章将详细讲解图的最短路...

    五分钟学算法
  • 数据结构与算法-求最短路径之迪杰斯特拉(Dijkstra)算法

    迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径,它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩...

    越陌度阡
  • 图论--差分约束系统

    求x1-x4的最大值,由题目给的式子1,2,4可得x1-x4>=11,我们来看图中最短路,x1到X4的最短距离也是11,也就是说差分约束系统就是将给定条件转化为...

    风骨散人Chiam
  • 最短路径算法(上)——迪杰斯特拉(Dijikstra)算法

    对于迪杰斯特拉算法的分支界限法解法请移步:利用分支界限法求解Dijikstra算法

    AI那点小事
  • 【算法】Dijkstra 算法:解决单源最短路径问题

    Dijkstra算法,中文名音译作迪杰斯特拉算法或戴克斯特拉算法,它是一个用来解决赋权图的单源最短路径问题的算法。

    叶锦鲤
  • 迪杰斯特拉算法(最短路径问题)

    假如有七个村庄(ABCDEFG),有个人从G点出发,到其他六个村庄的最短路径分别是多少?到A、B、F、E只有一条路,没得选,但是到C有两条路,可以是2 + 7,...

    贪挽懒月

扫码关注云+社区

领取腾讯云代金券