dijkstra算法 订阅
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 [1] 展开全文
迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。迪杰斯特拉算法主要特点是从起始点开始,采用贪心算法的策略,每次遍历到始点距离最近且未访问过的顶点的邻接节点,直到扩展到终点为止。 [1]
信息
别    称
狄克斯特拉算法 [1]
简    称
Dij算法 [1]
分    类
计算机算法 [1]
用    途
单源最短路径问题 [1]
中文名
迪克斯特拉算法 [1]
外文名
Dijkstra's Algorithm [2]
迪克斯特拉算法定义
Dijkstra算法一般的表述通常有两种方式,一种用永久和临时标号方式,一种是用OPEN, CLOSE表的方式,这里均采用永久和临时标号的方式。注意该算法要求图中不存在负权边。 [2] 
收起全文
精华内容
参与话题
问答
  • Dijkstra算法

    千次阅读 2016-02-17 15:49:55
    Dijkstra算法
    #include<stdio.h>
    #include<malloc.h>
    #include<string.h>
    #include<stack>
    using namespace std;
    #define MAX_VERTEX_NUM 20
    #define INFINITY 32768
    int visited[100];
    int path[MAX_VERTEX_NUM];
    typedef struct node1
    {
    	int adj;
    }gra;
    typedef struct node2
    {
    	gra arcs[100][100];
    	int vertex[100];
    	int vexnum,arcnum;
    }*graph,graph1;
    int locatevertex(graph &g,int v)
    {
    	int j=0,k;
    	for(k=0;k<g->vexnum;k++)
    	{
    		if(g->vertex[k]==v)
    		{
    			j=k;
    			break;
    		}	
    	}
    	return j;
    }
    void create(graph &g)
    {
    	int i,j,k,v1,v2,weight;
    	printf("请输入图的最大顶点数和最大弧数: ");
    	scanf("%d%d",&g->vexnum,&g->arcnum);
    	for(i=0;i<g->vexnum;i++)
    	{
    		for(j=0;j<g->vexnum;j++)
    		{
    			if(i==j)
    			g->arcs[i][j].adj=0;
    			else
    			g->arcs[i][j].adj=INFINITY;
    		}
    	}
    	printf("请输入图的各顶点值: ");
    	for(i=0;i<g->vexnum;i++)
    		scanf("%d",&g->vertex[i]);
    	for(k=0;k<g->arcnum;k++)
    	{
    		printf("请输入两顶点1,2表示1到2有关系: ");
    		scanf("%d%d%d",&v1,&v2,&weight);
    		i=locatevertex(g,v1);
    		j=locatevertex(g,v2);
    		g->arcs[i][j].adj=weight;
    	}
    }
    void shortestpath(graph &g,int n)
    {
    	int v0=0,k,min;
    	int dist[MAX_VERTEX_NUM];
        bool S[MAX_VERTEX_NUM];
    	for(int i=0;i<g->vexnum;i++)
    	{
    		S[i]=false;//对S初始化
    		dist[i]=g->arcs[v0][i].adj;//对dist初始化
    		if(dist[i]<INFINITY)
    		path[i]=0;
    		else
    		path[i]=-1;
    	}
    	S[v0]=true;
    	for(int t=1;t<=g->vexnum-1;t++)
    	{
    		min=INFINITY;
    		for(i=0;i<g->vexnum;i++)
    		{
    			if(!S[i]&&dist[i]<min)
    			{
    			 min=dist[i];
                 k=i;
    			}
    		}
    			if(min==INFINITY)
    			return ;
    		for(i=0;i<g->vexnum;i++)
    		{
    			if(!S[i]&&g->arcs[k][i].adj!=INFINITY&&(dist[k]+g->arcs[k][i].adj<dist[i])&&k!=i)
    			{
    				dist[i]=dist[k]+g->arcs[k][i].adj;
    				path[i]=k;
    			}
    		}
    		S[k]=true;
    	}
    	n=locatevertex(g,n);
    	int x=n;
    	while(n>=0)
    	{
    		printf("%d ",path[n]);
    		if(path[n]==0)
    		break;
    		n=path[n];
    	}
    	printf("最短路径长度为: ");
    	printf("%d\n",dist[x]);
    }
    int main()
    {
    	graph g;
    	int n;
    	g=(graph)malloc(sizeof(graph1));
    	create(g);
    	printf("请输入一个顶点求出它的最短路径: ");
    	scanf("%d",&n);
    	shortestpath(g,n);
    	return 0;
    }

    展开全文
  • 最短路径问题---Dijkstra算法详解

    万次阅读 多人点赞 2017-03-08 16:42:46
    前言 Nobody can go back and start a new beginning,but anyone can start today and make a new ending. Name:Willam Time:2017/3/8 1、最短路径问题介绍 问题解释: ...解决问题的算法:...

    前言
    Nobody can go back and start a new beginning,but anyone can start today and make a new ending.
    Name:Willam
    Time:2017/3/8

    1、最短路径问题介绍

    问题解释:
    从图中的某个顶点出发到达另外一个顶点的所经过的边的权重和最小的一条路径,称为最短路径

    解决问题的算法:

    这篇博客,我们就对Dijkstra算法来做一个详细的介绍

    2、Dijkstra算法介绍

    • 算法特点:

      迪科斯彻算法使用了广度优先搜索解决赋权有向图或者无向图的单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。

    • 算法的思路

      Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s。
      然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,OK,此时完成一个顶点,
      然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。
      然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    3、Dijkstra算法示例演示

    下面我求下图,从顶点v1到其他各个顶点的最短路径

    这里写图片描述

    首先第一步,我们先声明一个dis数组,该数组初始化的值为:
    这里写图片描述

    我们的顶点集T的初始化为:T={v1}

    既然是求 v1顶点到其余各个顶点的最短路程,那就先找一个离 1 号顶点最近的顶点。通过数组 dis 可知当前离v1顶点最近是 v3顶点。当选择了 2 号顶点后,dis[2](下标从0开始)的值就已经从“估计值”变为了“确定值”,即 v1顶点到 v3顶点的最短路程就是当前 dis[2]值。将V3加入到T中。
    为什么呢?因为目前离 v1顶点最近的是 v3顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得 v1顶点到 v3顶点的路程进一步缩短了。因为 v1顶点到其它顶点的路程肯定没有 v1到 v3顶点短.

    OK,既然确定了一个顶点的最短路径,下面我们就要根据这个新入的顶点V3会有出度,发现以v3 为弧尾的有: < v3,v4 >,那么我们看看路径:v1–v3–v4的长度是否比v1–v4短,其实这个已经是很明显的了,因为dis[3]代表的就是v1–v4的长度为无穷大,而v1–v3–v4的长度为:10+50=60,所以更新dis[3]的值,得到如下结果:
    这里写图片描述

    因此 dis[3]要更新为 60。这个过程有个专业术语叫做“松弛”。即 v1顶点到 v4顶点的路程即 dis[3],通过 < v3,v4> 这条边松弛成功。这便是 Dijkstra 算法的主要思想:通过“边”来松弛v1顶点到其余各个顶点的路程。

    然后,我们又从除dis[2]和dis[0]外的其他值中寻找最小值,发现dis[4]的值最小,通过之前是解释的原理,可以知道v1到v5的最短距离就是dis[4]的值,然后,我们把v5加入到集合T中,然后,考虑v5的出度是否会影响我们的数组dis的值,v5有两条出度:< v5,v4>和 < v5,v6>,然后我们发现:v1–v5–v4的长度为:50,而dis[3]的值为60,所以我们要更新dis[3]的值.另外,v1-v5-v6的长度为:90,而dis[5]为100,所以我们需要更新dis[5]的值。更新后的dis数组如下图:
    这里写图片描述

    然后,继续从dis中选择未确定的顶点的值中选择一个最小的值,发现dis[3]的值是最小的,所以把v4加入到集合T中,此时集合T={v1,v3,v5,v4},然后,考虑v4的出度是否会影响我们的数组dis的值,v4有一条出度:< v4,v6>,然后我们发现:v1–v5–v4–v6的长度为:60,而dis[5]的值为90,所以我们要更新dis[5]的值,更新后的dis数组如下图:
    这里写图片描述

    然后,我们使用同样原理,分别确定了v6和v2的最短路径,最后dis的数组的值如下:
    这里写图片描述

    因此,从图中,我们可以发现v1-v2的值为:∞,代表没有路径从v1到达v2。所以我们得到的最后的结果为:

    起点  终点    最短路径    长度
    v1    v2     无          ∞    
          v3     {v1,v3}    10
          v4     {v1,v5,v4}  50
          v5     {v1,v5}    30
          v6     {v1,v5,v4,v6} 60
    

    4、Dijkstra算法的代码实现(c++)

    • Dijkstra.h文件的代码
    /************************************************************/
    /*                程序作者:Willam                          */
    /*                程序完成时间:2017/3/8                    */
    /*                有任何问题请联系:2930526477@qq.com       */
    /************************************************************/
    //@尽量写出完美的程序
    
    #pragma once
    //#pragma once是一个比较常用的C/C++杂注,
    //只要在头文件的最开始加入这条杂注,
    //就能够保证头文件只被编译一次。
    
    #include<iostream>
    #include<string>
    using namespace std;
    
    /*
    本程序是使用Dijkstra算法实现求解最短路径的问题
    采用的邻接矩阵来存储图
    */
    //记录起点到每个顶点的最短路径的信息
    struct Dis {
        string path;
        int value;
        bool visit;
        Dis() {
            visit = false;
            value = 0;
            path = "";
        }
    };
    
    class Graph_DG {
    private:
        int vexnum;   //图的顶点个数
        int edge;     //图的边数
        int **arc;   //邻接矩阵
        Dis * dis;   //记录各个顶点最短路径的信息
    public:
        //构造函数
        Graph_DG(int vexnum, int edge);
        //析构函数
        ~Graph_DG();
        // 判断我们每次输入的的边的信息是否合法
        //顶点从1开始编号
        bool check_edge_value(int start, int end, int weight);
        //创建图
        void createGraph();
        //打印邻接矩阵
        void print();
        //求最短路径
        void Dijkstra(int begin);
        //打印最短路径
        void print_path(int);
    };
    
    • Dijkstra.cpp文件的代码
    #include"Dijkstra.h"
    
    //构造函数
    Graph_DG::Graph_DG(int vexnum, int edge) {
        //初始化顶点数和边数
        this->vexnum = vexnum;
        this->edge = edge;
        //为邻接矩阵开辟空间和赋初值
        arc = new int*[this->vexnum];
        dis = new Dis[this->vexnum];
        for (int i = 0; i < this->vexnum; i++) {
            arc[i] = new int[this->vexnum];
            for (int k = 0; k < this->vexnum; k++) {
                //邻接矩阵初始化为无穷大
                    arc[i][k] = INT_MAX;
            }
        }
    }
    //析构函数
    Graph_DG::~Graph_DG() {
        delete[] dis;
        for (int i = 0; i < this->vexnum; i++) {
            delete this->arc[i];
        }
        delete arc;
    }
    
    // 判断我们每次输入的的边的信息是否合法
    //顶点从1开始编号
    bool Graph_DG::check_edge_value(int start, int end, int weight) {
        if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) {
            return false;
        }
        return true;
    }
    
    void Graph_DG::createGraph() {
        cout << "请输入每条边的起点和终点(顶点编号从1开始)以及其权重" << endl;
        int start;
        int end;
        int weight;
        int count = 0;
        while (count != this->edge) {
            cin >> start >> end >> weight;
            //首先判断边的信息是否合法
            while (!this->check_edge_value(start, end, weight)) {
                cout << "输入的边的信息不合法,请重新输入" << endl;
                cin >> start >> end >> weight;
            }
            //对邻接矩阵对应上的点赋值
            arc[start - 1][end - 1] = weight;
            //无向图添加上这行代码
            //arc[end - 1][start - 1] = weight;
            ++count;
        }
    }
    
    void Graph_DG::print() {
        cout << "图的邻接矩阵为:" << endl;
        int count_row = 0; //打印行的标签
        int count_col = 0; //打印列的标签
        //开始打印
        while (count_row != this->vexnum) {
            count_col = 0;
            while (count_col != this->vexnum) {
                if (arc[count_row][count_col] == INT_MAX)
                    cout << "∞" << " ";
                else
                cout << arc[count_row][count_col] << " ";
                ++count_col;
            }
            cout << endl;
            ++count_row;
        }
    }
    void Graph_DG::Dijkstra(int begin){
        //首先初始化我们的dis数组
        int i;
        for (i = 0; i < this->vexnum; i++) {
            //设置当前的路径
            dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);
            dis[i].value = arc[begin - 1][i];
        }
        //设置起点的到起点的路径为0
        dis[begin - 1].value = 0;
        dis[begin - 1].visit = true;
    
        int count = 1;
        //计算剩余的顶点的最短路径(剩余this->vexnum-1个顶点)
        while (count != this->vexnum) {
            //temp用于保存当前dis数组中最小的那个下标
            //min记录的当前的最小值
            int temp=0;
            int min = INT_MAX;
            for (i = 0; i < this->vexnum; i++) {
                if (!dis[i].visit && dis[i].value<min) {
                    min = dis[i].value;
                    temp = i;
                }
            }
            //cout << temp + 1 << "  "<<min << endl;
            //把temp对应的顶点加入到已经找到的最短路径的集合中
            dis[temp].visit = true;
            ++count;
            for (i = 0; i < this->vexnum; i++) {
                //注意这里的条件arc[temp][i]!=INT_MAX必须加,不然会出现溢出,从而造成程序异常
                if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) {
                    //如果新得到的边可以影响其他为访问的顶点,那就就更新它的最短路径和长度
                    dis[i].value = dis[temp].value + arc[temp][i];
                    dis[i].path = dis[temp].path + "-->v" + to_string(i + 1);
                }
            }
        }
    
    }
    void Graph_DG::print_path(int begin) {
        string str;
        str = "v" + to_string(begin);
        cout << "以"<<str<<"为起点的图的最短路径为:" << endl;
        for (int i = 0; i != this->vexnum; i++) {
            if(dis[i].value!=INT_MAX)
            cout << dis[i].path << "=" << dis[i].value << endl;
            else {
                cout << dis[i].path << "是无最短路径的" << endl;
            }
        }
    }
    • main.cpp文件的代码
    #include"Dijkstra.h"
    
    
    //检验输入边数和顶点数的值是否有效,可以自己推算为啥:
    //顶点数和边数的关系是:((Vexnum*(Vexnum - 1)) / 2) < edge
    bool check(int Vexnum, int edge) {
        if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge)
            return false;
        return true;
    }
    int main() {
        int vexnum; int edge;
    
        cout << "输入图的顶点个数和边的条数:" << endl;
        cin >> vexnum >> edge;
        while (!check(vexnum, edge)) {
            cout << "输入的数值不合法,请重新输入" << endl;
            cin >> vexnum >> edge;
        }
        Graph_DG graph(vexnum, edge);
        graph.createGraph();
        graph.print();
        graph.Dijkstra(1);
        graph.print_path(1);
        system("pause");
        return 0;
    }

    输入:

    6 8
    1 3 10
    1 5 30
    1 6 100
    2 3 5
    3 4 50
    4 6 10
    5 6 60
    5 4 20

    输出:
    这里写图片描述

    从输出可以看出,程序的结果和我们之前手动计算的结果是一样的。

    展开全文
  • Dijkstra 算法

    2018-05-13 10:48:37
    MATLAB编写的Dijkstra 算法MATLAB编写的Dijkstra 算法MATLAB编写的Dijkstra 算法
  • dijkstra算法

    2020-04-08 21:04:45
    迪杰斯特拉算法(Dijkstra)是由荷兰计算机科学家狄克斯特拉于1959 年提出的,因此又叫狄克斯特拉算法。是从一个顶点到其余各顶点的最短路径算法,解决的是有权图中最短路径问题。
  • 简单易懂——Dijkstra算法讲解

    万次阅读 多人点赞 2018-02-18 00:22:46
    我的机器学习教程「美团」算法工程师带你入门机器学习 已经开始更新了,欢迎大家订阅~ 任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑...

    我的机器学习教程「美团」算法工程师带你入门机器学习   已经开始更新了,欢迎大家订阅~

    任何关于算法、编程、AI行业知识或博客内容的问题,可以随时扫码关注公众号「图灵的猫」,加入”学习小组“,沙雕博主在线答疑~此外,公众号内还有更多AI、算法、编程和大数据知识分享,以及免费的SSR节点和学习资料。其他平台(知乎/B站)也是同名「图灵的猫」,不要迷路哦~

     

     

    前言:



    相对于暴力简单的Floyd算法,Dijkstra算法更为有用且复杂度较为合理--O(N^2)。今天就为大家介绍一下这个算法。Dijkstra算法使用了广度优先搜索解决赋权有向图或者无向图单源最短路径问题,算法最终得到一个最短路径树。该算法常用于路由算法或者作为其他图算法的一个子模块。
     

    算法思路:

     

    Dijkstra算法采用的是一种贪心的策略,声明一个数组dis来保存源点到各个顶点的最短距离和一个保存已经找到了最短路径的顶点的集合:T,初始时,原点 s 的路径权重被赋为 0 (dis[s] = 0)。若对于顶点 s 存在能直接到达的边(s,m),则把dis[m]设为w(s, m),同时把所有其他(s不能直接到达的)顶点的路径长度设为无穷大。初始时,集合T只有顶点s

    然后,从dis数组选择最小值,则该值就是源点s到该值对应的顶点的最短路径,并且把该点加入到T中,此时完成一个顶点, 然后,我们需要看看新加入的顶点是否可以到达其他顶点并且看看通过该顶点到达其他点的路径长度是否比源点直接到达短,如果是,那么就替换这些顶点在dis中的值。 然后,又从dis中找出最小值,重复上述动作,直到T中包含了图的所有顶点。

    Dijkstra算法

    原理:这里不进行严格证明,Dijkstra的大致思想就是,根据初始点,挨个的把离初始点最近的点一个一个找到并加入集合,集合中所有的点的d[i]都是该点到初始点最短路径长度,由于后加入的点是根据集合S中的点为基础拓展的,所以也能找到最短路径。

    伪代码:

        清除所有点的标号;
        设d[0]=0,其他d[i]=INF;//INF是一个很大的值,用来替代正无穷
        循环n次 { 
            在所有未标号结点中,选出d值最小的结点x;
            给结点x标记;
            对于从x出发的所有边(x,y),更新d[y] = min{d[y], d[x]+w(x,y)} 
    


     

     

    与Floyd-Warshall算法一样这里仍然使用二维数组e来存储顶点之间边的关系,初始值如下。

     

    我们还需要用一个一维数组dis来存储1号顶点到其余各个顶点的初始路程,如下。

     

    我们将此时dis数组中的值称为最短路的“估计值”。

    Step 1:

           既然是求1号顶点到其余各个顶点的最短路程,那就先找一个离1号顶点最近的顶点。通过数组dis可知当前离1号顶点最近是2号顶点。当选择了2号顶点后,dis[2]的值就已经从“估计值”变为了“确定值”,即1号顶点到2号顶点的最短路程就是当前dis[2]值。为什么呢?你想啊,目前离1号顶点最近的是2号顶点,并且这个图所有的边都是正数,那么肯定不可能通过第三个顶点中转,使得1号顶点到2号顶点的路程进一步缩短了。因为1号顶点到其它顶点的路程肯定没有1号到2号顶点短

    Step 2:

           既然选了2号顶点,接下来再来看2号顶点有哪些出边呢。有2->3和2->4这两条边。先讨论通过2->3这条边能否让1号顶点到3号顶点的路程变短。也就是说现在来比较dis[3]和dis[2]+e[2][3]的大小。其中dis[3]表示1号顶点到3号顶点的路程。dis[2]+e[2][3]中dis[2]表示1号顶点到2号顶点的路程,e[2][3]表示2->3这条边。所以dis[2]+e[2][3]就表示从1号顶点先到2号顶点,再通过2->3这条边,到达3号顶点的路程。

    Step 3:

           我们发现dis[3]=12,dis[2]+e[2][3]=1+9=10,dis[3]>dis[2]+e[2][3],因此dis[3]要更新为10。这个过程有个专业术语叫做“松弛”。即1号顶点到3号顶点的路程即dis[3],通过2->3这条边松弛成功。这便是Dijkstra算法的主要思想:通过“边”来松弛1号顶点到其余各个顶点的路程。

     

           同理通过2->4(e[2][4]),可以将dis[4]的值从∞松弛为4(dis[4]初始为∞,dis[2]+e[2][4]=1+3=4,dis[4]>dis[2]+e[2][4],因此dis[4]要更新为4)。

    Step 4:

           刚才我们对2号顶点所有的出边进行了松弛。松弛完毕之后dis数组为:

     

           接下来,继续在剩下的3、4、5和6号顶点中,选出离1号顶点最近的顶点。通过上面更新过dis数组,当前离1号顶点最近是4号顶点。此时,dis[4]的值已经从“估计值”变为了“确定值”。下面继续对4号顶点的所有出边(4->3,4->5和4->6)用刚才的方法进行松弛。松弛完毕之后dis数组为:

     

           继续在剩下的3、5和6号顶点中,选出离1号顶点最近的顶点,这次选择3号顶点。此时,dis[3]的值已经从“估计值”变为了“确定值”。对3号顶点的所有出边(3->5)进行松弛。

           继续在剩下的5和6号顶点中,选出离1号顶点最近的顶点,这次选择5号顶点。此时,dis[5]的值已经从“估计值”变为了“确定值”。对5号顶点的所有出边(5->4)进行松弛。

     

           最后对6号顶点所有点出边进行松弛。因为这个例子中6号顶点没有出边,因此不用处理。到此,dis数组中所有的值都已经从“估计值”变为了“确定值”。

           最终dis数组如下,这便是1号顶点到其余各个顶点的最短路径。

     

           现在来总结一下刚才的算法。算法的基本思想是:每次找到离源点(上面例子的源点就是1号顶点)最近的一个顶点,然后以该顶点为中心进行扩展,最终得到源点到其余所有点的最短路径。基本步骤如下:

     

    • 将所有的顶点分为两部分:已知最短路程的顶点集合P和未知最短路径的顶点集合Q。最开始,已知最短路径的顶点集合P中只有源点一个顶点。我们这里用一个book[ i ]数组来记录哪些点在集合P中。例如对于某个顶点i,如果book[ i ]为1则表示这个顶点在集合P中,如果book[ i ]为0则表示这个顶点在集合Q中。

    • 设置源点s到自己的最短路径为0即dis=0。若存在源点有能直接到达的顶点i,则把dis[ i ]设为e[s][ i ]。同时把所有其它(源点不能直接到达的)顶点的最短路径为设为∞。

    • 在集合Q的所有顶点中选择一个离源点s最近的顶点u(即dis[u]最小)加入到集合P。并考察所有以点u为起点的边,对每一条边进行松弛操作。例如存在一条从u到v的边,那么可以通过将边u->v添加到尾部来拓展一条从s到v的路径,这条路径的长度是dis[u]+e[u][v]。如果这个值比目前已知的dis[v]的值要小,我们可以用新值来替代当前dis[v]中的值。

    • 重复第3步,如果集合Q为空,算法结束。最终dis数组中的值就是源点到所有顶点的最短路径。

     

    >>>关于作者

    CSDN 博客专家,2019-CSDN百大博主,计算机(机器学习方向)博士在读,业余Kaggle选手,有过美团、腾讯算法工程师经历,目前就职于Amazon AI lab。喜爱分享和知识整合。

    关注微信公众号,点击“学习资料”菜单即可获取算法、编程资源以及教学视频,还有免费SSR节点相送哦。其他平台(微信/知乎/B站),欢迎关注同名公众号「图灵的猫」~

    展开全文

空空如也

1 2 3 4 5 ... 20
收藏数 15,744
精华内容 6,297
关键字:

dijkstra算法