最短路問題的各種求法（二）Dijkstra算法

問題描述

給定一個n個點m條邊的有向圖，圖中可能存在重邊和自環，所有邊權均為正值。

請你求出1号點到n号點的最短距離，如果無法從1号點走到n号點，則輸出 −1。

樸素版Dijkstra算法

1. 把所有點到源點的距離初始化為0x3f3f3f3f3(正無窮),把源點到源點的距離初始化為0;

memset(dis,0x3f,sizeof dis);
    	dis[1]=0;
           

1. 在所有沒有被優化完的點(根據(st數組判斷)裡面找到到源點路徑最小的點,并用這個點到源點的距離來更新所有點到源點的距離

for(int j=1;j<=n;j++)
        {
            if(!st[j]&&(t==-1||dis[t]>dis[j]))t=j;
        }
        for(int j=1;j<=n;j++)
            dis[j]=min(dis[j],dis[t]+d[t][j]);
           

1. 将該點加入st數組表示已經被優化完

1. 重複2-3步直到所有點都加入st中

樸素版Dijkstra算法完整代碼

#include<iostream>
	#include<algorithm>
	#include<cstring>
	using namespace std;
	const int N=1e5+10,M=510;
	int d[M][M];
	bool st[M];
	int dis[M];
	int n,m;
	int Dijkstra()
	{
	    memset(dis,0x3f,sizeof dis);
	    dis[1]=0;
	    for(int i=1;i<=n;i++)
	    {
	        int t=-1;
	        for(int j=1;j<=n;j++)
	        {
	            if(!st[j]&&(t==-1||dis[t]>dis[j]))t=j;
	        }
	        st[t]=true;
	        for(int j=1;j<=n;j++)
	            dis[j]=min(dis[j],dis[t]+d[t][j]);
	    }
	    if(dis[n]>0x3f3f3f3f/2)return -1;
	    return dis[n];
	}
	int main()
	{
	    cin>>n>>m;
	    for(int i=1;i<=n;i++)
	    {
	        for(int j=1;j<=n;j++)
	        {
	            if(i==j)d[i][j]=0;
	            else d[i][j]=0x3f3f3f3f;
	        }
	    }
	    while(m--)
	    {
	        int a,b,c;
	        cin>>a>>b>>c;
	        d[a][b]=min(d[a][b],c);
	    }
	    cout<<Dijkstra()<<endl;
	}
           

堆優化版的Dijkstra算法

樸素版Dijkstra算法适用于稠密圖是以用鄰接矩陣來存儲，當m與n在一個數量級也就是稀疏圖的時候我們可以用鄰接表來存儲

因為每次都需要選擇路徑最小的邊來更新之後的每一條邊是以這裡可以用小根堆來存儲

定義小根堆

在小根堆裡面存取的是一個pair<路徑長度,點>因為pair是根據第一個元素進行排序的是以我們把路徑的長度放在pair的第一個位置

1. 将源點放入堆中并更新源點到源點的距離

heap.push({0,1});//距離，點
  		dis[1]=0;
           

2.當堆不空的時候每次取出距離源點最近的點，并對沒有被優化的每個點進行優化,如果有某個點的邊被優化了說明與這個點相連的點也可以進行優化，那樣我們就可以把這個點标記為已經被優化過并且将<這個點到源點的距離，這個點>入堆

while(!heap.empty())
	    {
	        PII t=heap.top();
	        heap.pop();
	        int dian=t.y;
	        if(!st[dian])
		    {
		        st[dian]=true;
		        for(int i=h[dian];i!=-1;i=ne[i])
		        {
		            int j=e[i];
		            if(dis[j]>dis[dian]+w[i])
		            {
		                dis[j]=dis[dian]+w[i];
	                   heap.push({dis[j],j});	                }
		            }
		         }
	    	 }
	      }
           

堆優化版Dijkstra算法完整代碼

#include<iostream>
	#include<cstring>
	#include<queue>
	#include<algorithm>
	using namespace std;
	typedef pair<int,int> PII;
	#define x first
	#define y second
	const int N=150010;
	int h[N],e[N],ne[N],w[N],idx;
	bool st[N];
	int dis[N];
	int m,n;
	void add(int a,int b,int c)
	{
	    e[idx]=b;
	    ne[idx]=h[a];
	    w[idx]=c;
	    h[a]=idx++;
	}
	int Dijkstra()
	{
	    priority_queue<PII, vector<PII>, greater<PII>> heap;
	    heap.push({0,1});//距離，點
	    dis[1]=0;
	    while(!heap.empty())
	    {
	        PII t=heap.top();
	        heap.pop();
	        int dian=t.y;
	        if(!st[dian])
	        {
	            st[dian]=true;
	            for(int i=h[dian];i!=-1;i=ne[i])
	            {
	                int j=e[i];
	                if(dis[j]>dis[dian]+w[i])
	                {
	                    dis[j]=dis[dian]+w[i];
	                    heap.push({dis[j],j});
	                }
	            }
	        }
	    }
	    if(dis[n]>0x3f3f3f3f/2)return -1;
	    return dis[n];
	}
	int main()
	{
	    scanf("%d %d",&n,&m);
	    memset(h,-1,sizeof h);
	    memset(dis,0x3f,sizeof dis);
	    while(m--)
	    {
	        int a,b,c;
	        scanf("%d %d %d",&a,&b,&c);
	        add(a,b,c);
	    }
	    cout<<Dijkstra();
	    return 0;
	}