Dijikstra演算法

演算法解決的問題：求已知頂點V0到其他頂點的最短路徑

圖中任意兩點間路徑可以表示為

Pxy = pxa + pab + pbc +· L + pcy （全部的p>0）

若求<x,y>的最短路徑，就是求 pxa,pab,pbc, pcy的最小值

而若使pab最小，前提是必須確定一個a，a又由pxa確認，

所以，迪杰斯特拉演算法本質上是一個遞推迭代的程序，知道了前一個才能知道后一個

定理一：與目標節點直接相連的多個節點中，權值最小的的節點與目標節點形成的路徑是最短路徑

證明：

先證充分性，即如果權值最小，那么是最短路徑

如圖所示，已知與v0直接相連的4個節點中，v1與v0直接相連且相較于其他直接相連的節點中路徑最小，所有v1與v0間的最短距離確認

設P表示最短路徑 P01表示從0到1的路徑可表示為

P01 = P0a + Pab + Pbc +· L + Pc1 （全部的p>0）

對于不同的路徑來說其少的只是 這個式子的中間項

設直接相連的P01 ‘= p01

非直接相連的 P01‘‘ = p0a + pa1；（a為中間節點）

又因為已知p01為所有直接相連節點中的最小值

所以有 p01 < p0a

有因為p＞0

所以P01‘ < P01’’恒成立，

證得其充分性

下面來證明其必要性

已知最短路徑，所以有 Po1 = p0a + pa1 最小

設數列Pn = p1 + p2 + p3 + p4 + …pn

Pn – Pn-1 = pn >0 恒成立，所以Pn為增數列

因此PnMin = p1 = p01

所以最小得路徑一定是直接相連的最小值

證得其必要性

演算法的執行思路

從前面的的遞推式子講起

同時也有

代入得

說明y到x的最短路徑 等于 x到c的最短路徑 + c到y的最短路徑

因此，我們需要對每個節點都進行一個標記，來說明它是否已經找到最短路徑

還需要一個陣列來存盤這個節點到我要找的目標節點的路徑長度

當所有節點都確定找到最短路徑后，這個長度陣列就是我所要找的最短路經

Path陣列的引入

前面提到過，任意兩個節點的路徑可以被描述為

而這個中間節點c是不確定的，我們求最短路徑的目的就是為了找到這個c；這個中間節點c同目標節點x，y一樣重要，是標識這個路徑的唯一手段，

因此，我們需要引入一個path陣列，來表明我的這條路徑中間經過的節點數，

這樣就可以說明x-y得最短路徑為 x -> a -> b -> c -> y

所以path陣列的含義是，y節點在找到x節點的最短路徑中，最后一個經過的其他節點

輔助向量的代碼展示

typedef struct Dijkstra
{
	bool final[vertex_MAX]; //用于標記某個頂點是否找到最短路徑
	int dis[vertex_MAX]; //記錄頂點得路徑長
	int path[vertex_MAX]; //記錄最短路徑時的直接前驅下
}Dijkstra;

這三個輔助向量來幫助我們有效執行迪杰斯特拉演算法

演算法執行流程

首先我們要先將我所要求到其他頂點最短路徑的那個頂點錄入final陣列，因為這個頂點到他自己的路徑永遠是0，且已經最小，因此將它自己的final置為true；

隨后，我們要找到所有從這個頂點指向出的弧，以第一次對dis陣列初始化

void Dijkstra_DN(MGraph* G,Dijkstra* D, int pos)
{
	D->final[pos] = true;
	for (int i = 0; i < G->vexnum; i++)
	{
		D->dis[i] = MAX;//當他為MAX時標識兩節點無直接路徑
		D->path[-1];
	}
	/*初始化輔助向量*/
	for (int w = FirstPoint(G, pos); w > 0; w = NextPoint(G, pos, w))
	{
		D->dis[w] = G->arcs[pos][w].adj;
		D->path[w] = pos;
	}
}

以如下圖為例，我們要求v0指到圖中其他所有節點的最短路徑，在經歷第一步演算法之后

輔助向量集變成以下形式

之后根據前面我們推導過的定理一（多個直接相連的節點中權最小的是最短路徑)

我們得出v4指向v0的是最短路徑

此時對v4進行修飾

此時已經確定

的最小情況，之后我們還要求P01 P02 P03 的最小路徑，所以我們可以以v4作為根節點進行判斷：

如果出現有一個與v4近鄰節點，final為false，且其到v4的距離 + v4到v0的距離小于當前其dis陣列的距離，就說明

P0x ＜ P04 + P4x

因此要修正dis的值

修正后輔助向量集如下圖

這時觀察到v3的dis最小，再確定v3，同時修正輔助向量集

之后觀察到v1最小，修正v1為，同時修正輔助向量集

之后就只剩下v2了，修正v2,同時修飾輔助向量集

完成手算的演算法流程

手算程序總結

手算的核心在于，判斷哪個節點需要修正，具體的修正程序

代碼實作

我們先來看看之前手算的流程圖

不難發現，我們總是在重復修正-初始化這個流程，所以我們可以從中抽象出兩個函式

int WhichNeedChange(MGraph* G, Dijkstra* D); //找到需要修正的頂點，并回傳其下標
void Revise(MGraph* G, Dijkstra* D, int w); //以w節點為根修正輔助向量

所以我們的程式可以簡化稱如下形式

void Dijkstra_DN(MGraph* G,Dijkstra* D, int pos)
{
	D->final[pos] = true;
	for (int i = 0; i < G->vexnum; i++)
	{
		D->dis[i] = MAX;//當他為MAX時標識兩節點無直接路徑
		D->path[-1];
	}
	/*初始化輔助向量*/
	for (int w = FirstPoint(G, pos); w > 0; w = NextPoint(G, pos, w))
	{
		D->dis[w] = G->arcs[pos][w].adj;
		D->path[w] = pos;
	}
	/*上面是初始化v0即輔助向量*/
	for (int i = 0; i < G->vexnum - 1; i++)
	{
		int w = WhichNeedChange(D);
		Revise(G, D, w);
	}
}

WhichNeedChange函式的實作

int WhichNeedChange(MGraph* G,Dijkstra* D)//找到需要修正的頂點，并回傳其下標
{
	int min = MAX;
	int ret = -1;
	for (int i = 0; i < G->vexnum; i++)
	{
		if (D->final[i] == false && D->dis[i] < min)
		{
			ret = i;
			min = D->dis[i];
		}
	}
	D->final[ret] = true;
	return ret;
}

這個函式難點在于理解中間的if判斷程序
需要修正的頂點需要滿足：
1，他需要沒有被確定過最短路徑
2，他的距離要是最小值

Revis修正函式的實作

讓我們再來回顧以下修正函式的執行思路
第一步，先找出給定節點的所有指向節點
第二步，看這些新找到節點路徑+給定節點的路徑 是否小于當前節點的路徑
即 判斷是否有 P0x ＜ P04 + P4x

void Revise(MGraph* G, Dijkstra* D, int w)//以w節點為根修正輔助向量
{
	for (int v = FirstPoint(G, w); v > 0; v = NextPoint(G, w, v))
	{
		if (G->arcs[w][v].adj + D->dis[w] < D->dis[v])
		{
			D->dis[v] = G->arcs[w][v].adj + D->dis[w];
			D->path[v] = w;
		}
	}
}

理解這個函式的難點再與理解if陳述句
這個陳述句的意思是，如果新開辟的路徑加上給定節點到v0的路徑小于原有節點到v0的路徑，就需要添加一個中間節點，以達到求出最短路徑的目的

整體代碼總覽

演算法核心代碼

int FirstPoint(MGraph* G, int v)
{
	int ret = -1;
	for (int j = 0; j <= G->vexnum; j++)
	{
		if (G->arcs[v][j].adj != MAX)
		{
			ret = j;
			break;
		}
	}
	return ret;
}
int NextPoint(MGraph* G, int v, int w)
{
	int ret = -1;
	for (int j = w; j <= G->vexnum; j++)
	{
		if (G->arcs[v][j].adj != MAX)
		{
			ret = j;
			break;
		}
	}
	return ret;
}
int WhichNeedChange(MGraph* G,Dijkstra* D)//找到需要修正的頂點，并回傳其下標
{
	int min = MAX;
	int ret = -1;
	for (int i = 0; i < G->vexnum; i++)
	{
		if (D->final[i] == false && D->dis[i] < min)
		{
			ret = i;
			min = D->dis[i];
		}
	}
	D->final[ret] = true;
	return ret;
}
void Revise(MGraph* G, Dijkstra* D, int w)//以w節點為根修正輔助向量
{
	for (int v = FirstPoint(G, w); v > 0; v = NextPoint(G, w, v))
	{
		if (G->arcs[w][v].adj + D->dis[w] < D->dis[v])
		{
			D->dis[v] = G->arcs[w][v].adj + D->dis[w];
			D->path[v] = w;
		}
	}
}
void Dijkstra_DN(MGraph* G,Dijkstra* D, int pos)
{
	D->final[pos] = true;
	for (int i = 0; i < G->vexnum; i++)
	{
		D->dis[i] = MAX;//當他為MAX時標識兩節點無直接路徑
		D->path[-1];
	}
	/*初始化輔助向量*/
	for (int w = FirstPoint(G, pos); w > 0; w = NextPoint(G, pos, w))
	{
		D->dis[w] = G->arcs[pos][w].adj;
		D->path[w] = pos;
	}
	for (int i = 0; i < G->vexnum - 1; i++)
	{
		int w = WhichNeedChange(G,D);
		Revise(G, D, w);
	}
}

臨接矩陣存盤結構以及初始化代碼

#include <stdio.h>
#define vertex_MAX 20
#define MAXSIZE 10
#define VRType int
#define VertexType char
#define MAX 99999
typedef struct Dijkstra
{
	bool final[vertex_MAX]; //用于標記某個頂點是否找到最短路徑
	int dis[vertex_MAX]; //記錄頂點得路徑長
	int path[vertex_MAX]; //記錄最短路徑時的直接前驅下
}Dijkstra;
typedef enum {
	DG, //有向圖
	DN, //有向網
	UDG, //無向圖
	UDN, //無向網
}GraphKind; //圖的型別

typedef struct ArcCell
{
	VRType adj; //矩陣元素的值，如果是網則是具體的值；如果是圖則只有1，0兩種
}ArcCell;

typedef struct MGraph
{
	GraphKind kind; //圖的型別
	int vexnum; //定點數
	int arcnum; //邊數
	VertexType vexs[MAXSIZE];
	ArcCell arcs[MAXSIZE][MAXSIZE];
}MGraph;

void creatGraph_DN(MGraph* G)
{
	G->kind = DN;
	printf("請輸入網的頂點數\n");
	scanf("%d", &(G->vexnum));
	printf("請輸入網的邊數\n");
	scanf("%d", &(G->arcnum));
	for (int i = 0; i < G->vexnum; i++)
	{
		scanf("%c", G->vexs[i]);
	}
	getchar();
	/*頂點錄入完畢*/
	for(int i = 0;i<G->vexnum;i++)
		for (int j = 0; j < G->vexnum; j++)
		{
			G->arcs[i][j].adj = MAX;
		}
	/*臨接矩陣初始化完畢*/
	for (int k = 0; k < G->arcnum; k++)
	{
		int i, j, w; 
		printf("請輸入弧<i,j>及其權w\n");
		scanf("%d %d %d", &i, &j, &k);
		G->arcs[i][j].adj = w;
	}
	/*各邊及其權值錄入完畢*/
}

文末總結

迪杰斯特拉演算法的實質就是不斷重復《找待修正節點》 —《修正輔助向量》這一程序
只要把握了這個特點，理解迪杰斯特拉演算法就不難了
在研究生考試的初試中，我們只需要掌握迪杰斯特拉演算法的手算即可！！