转载 | Dijstra算法

傷城~ 2021-10-31 15:48 288阅读 0赞

## 算法思路—— ##

1.  指定一个节点，例如我们要计算 'A' 到其他节点的最短路径
2.  引入两个集合（S、U），**S集合**包含已求出的最短路径的点（以及相应的最短长度），**U集合**包含未求出最短路径的点（以及A到该点的路径，**注意 如上图所示，`A->C`由于没有直接相连 初始时为∞**）
3.  初始化两个集合，S集合初始时 只有当前要计算的节点，`A->A = 0`，  
    U集合初始时为 `A->B = 4, A->C = ∞, A->D = 2, A->E = ∞`，**敲黑板！！！接下来要进行核心两步骤了**
4.  从U集合中找出路径最短的点，加入S集合，例如 `A->D = 2`
5.  更新U集合路径，`if ( 'D 到 B,C,E 的距离' + 'AD 距离' < 'A 到 B,C,E 的距离' )` 则更新U
6.  循环执行 4、5 两步骤，直至遍历结束，得到A 到其他节点的最短路径

1.选定A节点并初始化，如上述步骤3所示

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LTZmNjJlZWQxZmYxYzY1ZDMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTIvZm9ybWF0L3dlYnA][]

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

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LThlOTUwMzJmNTcxNzU3MTgucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81ODQvZm9ybWF0L3dlYnA][]

3.这时候 `A->B, A->C` 都为3，没关系。其实这时候他俩都是最短距离，如果从算法逻辑来讲的话，会先取到B点。而这个时候 if 条件变成了 `if ( 'B 到 C,E 的距离' + 'AB 距离' < 'A 到 C,E 的距离' )` ，**如图所示这时候`A->B`距离 其实为 `A->D->B`**

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LWRjODJjMzM2YjZmZmUxMGUucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTUvZm9ybWF0L3dlYnA][]

1.  思路就是这样，往后就是大同小异了

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LTc4OTgxYmM0YTkzMmNiNzgucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTMvZm9ybWF0L3dlYnA][]

1.  算法结束

![aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LThmNjU5NzdiZWViZDZiNGMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81ODkvZm9ybWF0L3dlYnA][]

来源：https://www.jianshu.com/p/ff6db00ad866

--------------------

## 实现—— ##

[https://blog.csdn.net/lbperfect123/article/details/84281300][https_blog.csdn.net_lbperfect123_article_details_84281300]

![20181120091404344.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicGVyZmVjdDEyMw_size_16_color_FFFFFF_t_70][]

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<iostream>
    #define Inf 0x3f3f3f3f
     
    using namespace std;
     
    int map[1005][1005];
     
    int vis[1005],dis[1005];
    int n,m;//n个点，m条边
     
    void Init ()
    {
    	memset(map,Inf,sizeof(map));
    	for(int i=1;i<=n;i++)
    	{
    		map[i][i]=0;
    	}
    }
     
    void Getmap()
    {
    	int u,v,w;
        for(int t=1;t<=m;t++)
    	{
    	  	scanf("%d%d%d",&u,&v,&w);
    	  	if(map[u][v]>w)
    		  {
    		  map[u][v]=w;
    		  map[v][u]=w;
    	      }
    	}	
    	
    }
     
    void Dijkstra(int u)
    {
    	memset(vis,0,sizeof(vis));
    	for(int t=1;t<=n;t++)
    	{
    		dis[t]=map[u][t];
    	}
    	vis[u]=1;
    	for(int t=1;t<n;t++)
    	{
    		int minn=Inf,temp;
    		for(int i=1;i<=n;i++)
    		{
    			if(!vis[i]&&dis[i]<minn)
    			{
    				minn=dis[i];
    				temp=i;
    			}
    		}
    		vis[temp]=1;
    		for(int i=1;i<=n;i++)
    		{
    			if(map[temp][i]+dis[temp]<dis[i])
    			{
    				dis[i]=map[temp][i]+dis[temp];
    			}
    		}
    	}
    	
    }
     
    int main()
    {
    	
    	scanf("%d%d",&m,&n);
    	Init();
    	Getmap();
    	Dijkstra(n);
    	printf("%d\n",dis[1]);
    	
    	
    	return 0;
    }

[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LTZmNjJlZWQxZmYxYzY1ZDMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTIvZm9ybWF0L3dlYnA]: /images/20211031/88215a4fe5ef47e9bef9799ea97bfe6f.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LThlOTUwMzJmNTcxNzU3MTgucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81ODQvZm9ybWF0L3dlYnA]: /images/20211031/76638d5881a4469d8d0f605901a7c994.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LWRjODJjMzM2YjZmZmUxMGUucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTUvZm9ybWF0L3dlYnA]: /images/20211031/c8441b9a48dc432ea54890bc66b198d1.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LTc4OTgxYmM0YTkzMmNiNzgucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81OTMvZm9ybWF0L3dlYnA]: /images/20211031/cf8ba08f17d64b5abd522785185deef5.png
[aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LThmNjU5NzdiZWViZDZiNGMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81ODkvZm9ybWF0L3dlYnA]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQtaW1hZ2VzLmppYW5zaHUuaW8vdXBsb2FkX2ltYWdlcy85OTQ5OTE4LThmNjU5NzdiZWViZDZiNGMucG5nP2ltYWdlTW9ncjIvYXV0by1vcmllbnQvc3RyaXAlN0NpbWFnZVZpZXcyLzIvdy81ODkvZm9ybWF0L3dlYnA
[https_blog.csdn.net_lbperfect123_article_details_84281300]: https://blog.csdn.net/lbperfect123/article/details/84281300
[20181120091404344.png]: https://img-blog.csdnimg.cn/20181120091404344.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicGVyZmVjdDEyMw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20181120091752405.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xicGVyZmVjdDEyMw==,size_16,color_FFFFFF,t_70