没有楼的楼长的博客

Dijkstra#

dijkstra 是一個運用了貪心思想和廣度優先搜索的單源最短路算法，它的時間複雜度比 SPFA 的時間複雜度稍低，很適合在沒有負邊權且不是隨機數據（卡 SPFA）的情況下使用。

dijkstra 運用了貪心的策略，將每個點與起點的距離存到一個 dis 數組裡，若這個點不與起點直接相連則將其的距離看做是無窮大（在這裡用$0x7fffffff$（int 的最大值）代替）。將已經處理好的（確定是最短路的）頂點標記在一個數組裡。

那要怎麼處理呢？

我們先把與起點直接相連的點遍歷一遍，找出與起點距離最小的點，我們在這裡稱之為 A 點，把它標記為處理好。為什麼這樣就把 A 點處理好了呢？因為按照貪心的思想，A 點如果與起點距離最小，那從起點到別的點再到 A 點的話距離一定會比從起點直接到 A 點的距離大（這也是為什麼 dijkstra 不適用有負邊權的圖的原因）。然後我們把所有與 A 點相連的點全都遍歷一遍，如果從起點到 A 點再到這個點的距離比直接從起點到這個點的距離小的話，那麼我們就更新起點到這個點的距離，術語叫做 “鬆弛”。以此類推，一直到所有的頂點都鬆弛完了為止。

上圖開講#

首先我們構造這樣一個圖

以 A 為起點，dis 數組是這樣的（下標從 0 開始）

我們遍歷一遍 dis 數組，找出離 A 最近的點 E，並把它標記為已經處理好的點（綠色）。

然後我們遍歷與 E 相連的點，比較從起點到 E 點再到這個點的距離，如果比從起點直接到這個點的距離短，就更新起點到這個點的距離。如 B 點，從起點到 E 點再到 B 點的距離（15）比從起點直接到 B 點的距離小（$\infty$），於是我們更新 dis 數組中到 B 點的距離。（紅色表示處理過但不確定，不在程序中標記，只是為了講著方便）

然後遍歷到 F 點，可得 A-B-F 的距離（9）小於 A-F 的距離（10），於是更新 dis 數組中 A-F 的距離

與 E 點相連的點遍歷完後，我們再次遍歷 dis 數組並找出沒有處理過的離 A 最近的點，重複 E 點的步驟，直到所有的點都處理完為止。

標記 F 點為確定的點

遍歷與 F 點相連的點並更新距離
沒有與 F 點相連的點，遍歷 dis 數組找下一個

標記 B 點為確定的點

遍歷與 B 點相連的點並更新距離
沒有與 B 點相連的點，遍歷 dis 數組找下一個

標記 C 為確定的點

遍歷與 C 點相連的點並更新距離

找到 D 點，$20+5<\infty$，更新 A 點到 D 點的距離為 25

沒有與 C 點相連的點了，遍歷 dis 數組找下一個

標記 D 為確定的點

所有的點都更新完了，我們就得到了 A 點到所有點的最短路徑長度

這就是利用 Dijkstra 尋找單源最短路徑的方法。

為啥不能用在帶負邊權的圖上呢#

那為什麼 Dijkstra 不能用在帶有負邊權的圖上呢？
讓我們用一個圖來解釋一下

以 A 點為起點，最初的 dis 數組是這樣的

如果按照 Dijkstra 的步驟來，第一步我們會把 C 點確定

然鹅 5 並不是 A 點到 C 點的最短距離，A-B-C 的距離是 0，這明顯比 5 要小，但是我們已經確定了 A-C 的距離，我們就不會進行更新，導致輸出一個錯誤的答案

Dijkstra 真是個難學的算法

最後是你們最想要的

模板#

鄰接矩陣存儲（起點為 1）：

void dijkstra()
{
    memset(dis,127/3,sizeof(dis));//初始化
    v[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;++i)
    {
        int k=0;
        for(int j=1;j<=n;++j)//找出距離最近的點
            if(!v[j]&&(k==0||dis[j]<dis[k]))
                k=j;
        v[k]=1;//加入集合
        for(int j=1;j<=n;++j)//鬆弛
            if(!v[j]&&dis[k]+a[k][j]<dis[j])
                dis[j]=dis[k]+a[k][j];
    }
}

鄰接鏈表存儲（加堆優化）：

using namespace std;
const int maxn=250;
struct edge{
	int to,dis,next;
	//定義邊的結構體
};
edge e[maxn*2]; //邊的鏈表
int head[maxn],dis[maxn],cnt;
bool vis[maxn];
int n,a,b;

inline void add_edge(int u,int v,int d){
	cnt++;//把邊加進去
	e[cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;//存儲上一條邊
}

struct node{
	int dis;//點的結構體，dis為A點到這個點的距離
	int pos;
	bool operator <(const node &x)const
	{
		return x.dis<dis;//重載運算符，要不然c++沒法比
	}
};

priority_queue<node> q;

inline void dij(){
	dis[a]=0;
	q.push((node){0,a});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis; //鬆弛
				if(!vis[y]){
					q.push((node){dis[y],y});//入隊
				}
			}
		}
	}
}

我代碼好醜