迪傑斯特拉(Dijkstra) —— 最短路算法

Dijkstra是最短路基礎算法之一（還有判負環的SPFA和多源最短路的Floyd），但在正常情況下Dijkstra是最快的，也同樣是最難打的其實都不是很難，接下來我們來談談具體算法：

1.适用範圍

沒有負環（就是走一圈就可以将路程變小，沒有最短路的圖）的單源最短路（就是隻有一個起點的最短路）；

2.基本思路：

已知量隻有每條邊的權值，但我們可以很容易的想到起點到起點的最短路是0，于是我們可以一開始就将定義一個dij數組來存從起點到每個點的最短路的長度，是以自然dij[1]（假設1是起點）就為0，而想要更新其他的就要将除1以外的指派為MAXN（一個極大值）；

因為沒有負的權值，是以很容易證明在已有的dij數組中的最小值是不會再被其他點更新的，是以每一次我們都将已有的最短的那個數對應的節點取出，再由它來更新它所連接配接的點（如果到最小值的那個點的值加上權值依然小于它所連接配接的那個節點的已有的最小值就更新它），同樣不能忘了将這個最小值的點當機（開個bool數組）以免重複計算；

由于每次取出一個點又凍住那個點，我們不難想到在有n個點的情況下隻需要循環n次就行了；

3.實際操作：

輸入：

先用鄰接表存圖（注意是單向圖還是雙向），記錄起點終點；

初值：

先memset（dij，0x3f，sizeof（dij）），再将dij[1]指派為0；

Dijkstra：

用一個循環n次的for循環來做取點以及當機的操作，每次取出最小的點再循環尋找每一個與它相連的節點并更新需要更新的節點；

輸出：

按題目要求輸出即可；

特殊處理（輸出路徑）：

前面我們已經找到最短路，那麼輸出路徑隻需要再開一個數組，在更新最短路長度的同時記錄是哪一個點更新的它就行了，最後用倒推的方式輸出即可（可以類比背包問題找方案的方法）；

4.例題：

騎車比賽

Description

小信準備去參加騎車比賽，比賽在 n 個城市間進行，編号從 1 到 n。選手們都從城市 1 出發，終點在城市 n。

已知城市間有 m 條道路，每條道路連接配接兩個城市，注意道路是雙向的。現在小信知道了他經過每條道路需要花費的時間，他想請你幫他計算一下，他這次比賽最少需要花多少時間完成。

Input

第一行輸入兩個整數 n,m（1≤n≤1,000,1≤m≤5,000），分别代表城市個數和道路總數。接下來輸入 m 行，每行輸入三個數字 a,b,c（1≤a,b≤n,1≤c≤200），分别代表道路的起點和道路的終點，以及小信騎車通過這條道路需要花費的時間。保證輸入的圖是連通的。

Output

輸出一行，輸出一個整數，輸出小信完成比賽需要的最少時間。

Sample Input 1

    5 6

    1 2 2

    2 3 3

    2 5 5

    3 4 2

    3 5 1

    4 5 1

Sample Output 1

     6

Dijkstra經典例題就是個裸題，直接上代碼

代碼1（無優化）

#include<bits/stdc++.h>
using namespace std;
struct node//結構體代表每個節點的資料{
		int to,ti;//to代表到達的節點，ti代表所需時間
node(int a,int b) { //構造函數（不會可以不用）
	to=a;
	ti=b;
}
node() {}
};
int main() {
	int n,m,x,y,z;
	cin>>n>>m;
	map<int,vector<node> > ma;//用映射來存節點以及的其對應的邊
	for(int i=1; i<=m; i++) {
		cin>>x>>y>>z;
		ma[x].push_back(node(y,z));//注意本題是雙向圖
		ma[y].push_back(node(x,z));
	}
	int st=1,dis[n+1],vis[n+1];//st代表目前最小的值的節點一開始當然是1
	memset(dis,0x3f,sizeof(dis));//先賦一個極大值
	memset(vis,0,sizeof(vis));//表示是否當機了節點
	dis[1]=0;//起點為0；
	for(int j=1; j<=n; j++) { //循環取（當機）點
		//cout<<st<<endl;
		int minn=1e+8,tmp;
		vis[st]=1;//當機節點
		int l=ma[st].size();
		for(int i=0; i<l; i++) { //枚舉、更新
			if(!vis[ma[st][i].to]) {
				dis[ma[st][i].to]=min(dis[ma[st][i].to],dis[st]+ma[st][i].ti)
			}
		}
		for(int i=1; i<=n; i++) { //找已有的最小值
			if(!vis[i]&&dis[i]<minn) {
				minn=dis[i];
				tmp=i;
			}
		}
		st=tmp;//更新
	}
	cout<<dis[n];
}
           

仔細讀代碼便可以發現，找最小值的操作會浪費大量時間（O（n）），那可不可以優化成O（1）呢？？我們可以用一個神奇的資料類型——set（可參考基礎資料結構），set有天然排序的性質，我們把這種優化叫做堆優化

堆優化

#include<bits/stdc++.h>
using namespace std;
struct node { //結構體代表每條邊的資料
	int to,q,next;//to表示邊連接配接的節點，q代表權值，next代表這條邊的下一個邊
	node(int a,int b,int c) {
		to=a;
		q=b;
		next=c;
	}
	node() {}
} ma[1000001]; //ma用于存邊
set<pair<int,int> > st;//優化的set，分别存dij[i]和i
int k,head[1000001],dij[1000001],n,m;//head表示每一個節點，由head找到節點對應的邊
bool ok[1000001];
void add(int a,int b,int c) { //用于存a到b用c時間的邊
	ma[++k]=node(b,c,head[a]);
	head[a]=k;
}
int main() {
	memset(dij,0x3f,sizeof(dij));
	memset(head,-1,sizeof(head));
	cin>>n>>m;
	for(int i=1; i<=m; i++) {
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,z);
		add(y,x,z);
	}
	dij[1]=0;
	st.insert(make_pair(0,1));
	for(int i=1; i<=n; i++) {
		int u=st.begin()->second;//->為指針找到最小值的節點
		ok[u]=1;//當機節點
		st.erase(st.begin());//删除節點
		for(int j=head[u]; ~j; j=ma[j].next) { //~j表示j是否為-1
			if(!ok[ma[j].to]&&dij[u]+ma[j].q<dij[ma[j].to]) {
				st.erase(make_pair(dij[ma[j].to],ma[j].to));
				dij[ma[j].to]=ma[j].q+dij[u];
				st.insert(make_pair(dij[ma[j].to],ma[j].to));
			}
		}
	}
	cout<<dij[n];
}
           

注：轉載時有删改

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

作者：Journey.R 

來源：CSDN 

原文：https://blog.csdn.net/GENE1997/article/details/83031595?utm_source=copy 

版權聲明：本文為部落客原創文章，轉載請附上博文連結！