單源最短路徑問題（Dijkstra算法）

文章目錄

• • • 一、介紹
    • 二、實戰
    • 三、時間複雜度
    • 四、用優先隊列優化
    • 最小堆

無向圖

單源最短路徑

Dijkstra算法

最小堆

一、介紹

算法描述

二、實戰

(圖檔來源未知)

求上圖從Start到Destination的最短路徑

• python解法

INF = 1e10        # 無限大
node_number = 16  # node的數目
route_length = [  # node節點間的距離矩陣
[INF,   4, INF,   2, INF, INF,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 節點0
[  4, INF,   2, INF,   7,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 節點1
[INF,   2, INF,   5, INF,   2, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF], # 節點2
[  2, INF,   5, INF, INF, INF, INF,   8, INF, INF, INF, INF, INF, INF, INF, INF], # 節點3
[INF,   7, INF, INF, INF,   5, INF, INF, INF, INF,   6, INF,   8, INF,   9, INF], # 節點4
[INF,   3,   2, INF,   5, INF, INF, INF,   3, INF,   9, INF, INF, INF, INF, INF], # 節點5
[  3, INF, INF, INF, INF, INF, INF,   5,   4,   7, INF, INF, INF, INF, INF, INF], # 節點6
[INF, INF, INF,   8, INF, INF,   5, INF, INF,   1, INF,   8, INF, INF, INF, INF], # 節點7
[INF, INF, INF, INF, INF,   3,   4, INF, INF, INF,   4, INF, INF, INF, INF, INF], # 節點8
[INF, INF, INF, INF, INF, INF,   7,   1, INF, INF,   4, INF, INF, INF, INF, INF], # 節點9
[INF, INF, INF, INF,   6,   9, INF, INF,   4,   4, INF,   4, INF,   7, INF, INF], # 節點10
[INF, INF, INF, INF, INF, INF, INF,   8, INF, INF,   4, INF, INF,   2, INF, INF], # 節點11
[INF, INF, INF, INF,   8, INF, INF, INF, INF, INF, INF, INF, INF,   8, INF,   9], # 節點12
[INF, INF, INF, INF, INF, INF, INF, INF, INF, INF,   7,   2,   8, INF,   4,   8], # 節點13
[INF, INF, INF, INF,   9, INF, INF, INF, INF, INF, INF, INF, INF,   4, INF,   3], # 節點14
[INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF,   9,   8,   3, INF]] # 節點15
cost = [INF] * node_number    # 從起點到各個節點間的距離初始化為INF
pre_node= [0] * node_number   # 記錄索引對應節點的上一個節點（友善列印路徑）

cost[0]=0  # cost of start to start is 0. After that, cost is: [0,INF,INF,...INF]
L = [i for i in range(node_number)]  # list of node.

while L:
    minimum=INF
    min_cost_node=0
    for i in L:  # find the index of the node which has the minimum cost in list 'cost'.
        if minimum>cost[i] and i!=-1:  # i=-1 means that node 'i' is deleted in the previous loop.
            minimum=cost[i]
            min_cost_node=i
    if min_cost_node==15:   # 15 is the end node we want to go.
        break
    L[min_cost_node]=-1  # delete the node in list 'L'
    for index,val in enumerate(route_length[min_cost_node]):  # route_length[min_cost_node] is one row of the matrix.
        '''
        For example,when min_cost_node is node '0',
        then the row is [INF,   4, INF,   2, INF, INF,   3, INF, INF, INF, INF, INF, INF, INF, INF, INF]. # ノード0
        in this 'for' loop, (index,val) can be (0,INF),(1,4),(2,INF),(3,2)...(15,INF). 
        '''
        if val<INF:    # val<INF means that I can directly go to node 'index' from node 'min_cost_node'.
            if cost[index]>cost[min_cost_node]+val:
                '''
                Update the list 'cost'.Because we find a path 
                which go through node 'min_cost_node' costs fewer then the path found previously.
                '''
                cost[index] = cost[min_cost_node] + val
                '''
                Because this path has a road from node 'min_cost_node' to node 'index',
                we record this road.Just let node 'min_cost_node' be the previous node of node 'index'.
                '''
                pre_node[index]=min_cost_node

# path is the result we find.
path=[]
vertex=15
while vertex!=0:
    path.append(vertex)
    vertex=pre_node[vertex]
path.append(0)
print('The minimum cost path is: ')
for i in range (len(path)-1,0,-1):
    print(path[i],'-->',end='')
print(path[0])
print('The cost is: ',cost[15])

           

• C++解法
  • 主要函數：

/*
計算從節點's'開始的最短路徑
結果存儲在數組D中
*/
void Dijkstra(graph* G, int* D, int s) {
	int i, v, w;
	for (i = 0; i < G->n(); ++i) {
		v = minVertex(G, D);
		if (D[v] == INF)
			return; //說明節點v是孤立點，不可到達
		G->setMark(v, VISITED);
		for (w = G->first(v); w < G->n(); w = G->next(v, w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				/*頂點w的上一個頂點是v*/
				path[w] = v;
			}
	}
}
           

• 完整代碼

主函數所在檔案

#include<iostream>
#include<stack>
#include "graphm.h"
#include<string.h>
const int INF = 1e8;
const int VISITED = 1;
const int N = 16;
int path[1000];
int D[N];
/*找到目前花費最小的頂點*/
int minVertex(graph* G, int* D) {
	int i, v = -1;
	/*從頭開始，找到一個沒有被通路過的頂點，指派給v*/
	for(i=0;i<G->n();++i)
		if (G->getMark(i) == UNVISITED) { v = i; break; }
	/*與上面的頂點比較花費大小，找到花費最小的未被通路的頂點*/
	for (i++; i < G->n(); i++)
		if (G->getMark(i) == UNVISITED && (D[i] < D[v]))
			v = i;
	return v;
}

/*
計算從節點's'開始的最短路徑
結果存儲在數組D中
*/
void Dijkstra(graph* G, int* D, int s) {
	int i, v, w;
	for (i = 0; i < G->n(); ++i) {
		v = minVertex(G, D);
		if (D[v] == INF)
			return; //說明節點v是孤立點，不可到達
		G->setMark(v, VISITED);
		for (w = G->first(v); w < G->n(); w = G->next(v, w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				/*頂點w的上一個頂點是v*/
				path[w] = v;
			}
	}
}

int main() {
	int matrix[N][N] = {// node節點間的距離矩陣
		{INF, 4, INF, 2, INF, INF, 3, INF, INF, INF, INF, INF, INF, INF, INF, INF} , // 節點0
			{4, INF, 2, INF, 7, 3, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}, // 節點1
			{INF, 2, INF, 5, INF, 2, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF}, // 節點2
			{2, INF, 5, INF, INF, INF, INF, 8, INF, INF, INF, INF, INF, INF, INF, INF}, // 節點3
			{INF, 7, INF, INF, INF, 5, INF, INF, INF, INF, 6, INF, 8, INF, 9, INF}, // 節點4
			{INF, 3, 2, INF, 5, INF, INF, INF, 3, INF, 9, INF, INF, INF, INF, INF}, // 節點5
			{3, INF, INF, INF, INF, INF, INF, 5, 4, 7, INF, INF, INF, INF, INF, INF}, // 節點6
			{INF, INF, INF, 8, INF, INF, 5, INF, INF, 1, INF, 8, INF, INF, INF, INF}, // 節點7
			{INF, INF, INF, INF, INF, 3, 4, INF, INF, INF, 4, INF, INF, INF, INF, INF}, // 節點8
			{INF, INF, INF, INF, INF, INF, 7, 1, INF, INF, 4, INF, INF, INF, INF, INF}, // 節點9
			{INF, INF, INF, INF, 6, 9, INF, INF, 4, 4, INF, 4, INF, 7, INF, INF}, // 節點10
			{INF, INF, INF, INF, INF, INF, INF, 8, INF, INF, 4, INF, INF, 2, INF, INF}, // 節點11
			{INF, INF, INF, INF, 8, INF, INF, INF, INF, INF, INF, INF, INF, 8, INF, 9}, // 節點12
			{INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 7, 2, 8, INF, 4, 8}, // 節點13
			{INF, INF, INF, INF, 9, INF, INF, INF, INF, INF, INF, INF, INF, 4, INF, 3}, // 節點14
	       {INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, INF, 9, 8, 3, INF}// 節點15
	}; 
	memset(path, -1, sizeof(path));
	graph* G = new graphm(N);
	for (int i = 0; i < N; ++i)
		for (int j = 0; j < N; ++j)
			G->setEdge(i, j, matrix[i][j]);
	for (int i = 0; i < N; ++i)
		D[i] = INF;
	D[0] = 0;          //頂點和頂點自己之間的距離為0
	Dijkstra(G, D, 0);
	std::cout << "從起點到終點的最短路徑是： ";
	int prev = N - 1;
	std::stack<int>pth;
	while (path[prev] != -1) {
		pth.push(path[prev]);
		prev = path[prev];
	}
	while (!pth.empty()) {
		std::cout << pth.top() << " --> ";
		pth.pop();
	}
	std::cout <<N-1<< std::endl;
	std::cout <<"總距離為： "<< D[N - 1] << std::endl;
}

           

檔案2：graph.h(圖的抽象類)

#pragma once
/*程式代碼源于《資料結構與算法C++描述第三版》*/

/*
圖的抽象類，這裡假設圖被建立後，圖的頂點數目不變
*/
class graph
{
private:
	void operator=(const graph&) {}    //保護圖，防止圖被顯示指派
	graph(const graph&) {}       //複制構造函數也設為私有
public:
	graph() {}         //預設構造函數
	virtual ~graph() {}  //析構函數

	//初始化有n個節點的圖
	virtual void Init(int n) = 0;

	//傳回圖的頂點數目和邊的數目
	virtual int n() = 0;
	virtual int e() = 0;

	//傳回頂點'v'的第一個相鄰頂點
	virtual int  first(int v) = 0;

	//傳回頂點v的下一個相鄰頂點（在頂點'w'之後）
	virtual int next(int v, int w) = 0;

	//設定邊的權重，i,j是頂點，wgt是邊的權重
	virtual void setEdge(int i, int j, int wgt)=0;

	//删除邊，i,j是頂點
	virtual void delEdge(int i, int j) = 0;

	//判斷邊是否在圖中，i,j是頂點,如果邊（i,j）權重不為0傳回true
	virtual bool isEdge(int i, int j) = 0;

	//傳回邊的權重，i,j是頂點，
	virtual int weight(int i, int j) = 0;

	//擷取或者設定頂點'v'的标志值，友善确認這個頂點之前是否被我們通路過
	//val是要設定的值
	virtual int getMark(int v) = 0;
	virtual void setMark(int v, int val) = 0;
};


           

檔案3：graphm.h(圖的相鄰矩陣實作)

#pragma once
#include"graph.h"
const int UNVISITED = 0;
class graphm: public graph
{
private:
	int numVertex, numEdge;   //頂點和邊的數目
	int** matrix;             //相鄰矩陣
	int* mark;				  //标記數組
public:
	graphm(int numVert) {     //構造函數
		Init(numVert);
	}
	~graphm()   //析構函數
	{
		delete[]mark;
		for (int i = 0; i < numVertex; ++i)
			delete[]matrix[i];
		delete []matrix;
	}

	//初始化有n個頂點的圖
	void Init(int n) {
		int i;
		numVertex = n;
		numEdge = 0;
		mark = new int[n];
		//初始化标記數組
		for (i = 0; i < numVertex; ++i)
			mark[i] = UNVISITED;
		matrix = new int* [numVertex];
		for (i = 0; i < numVertex; ++i)
			matrix[i] = new int[numVertex];
		for (i = 0; i < numVertex; ++i)
			for (int j = 0; j < numVertex; ++j)
				matrix[i][j] = 0;    //0代表邊不存在
	}

	//頂點數目
	int n() { return numVertex; }
	
	//邊的數目
	int e() { return numEdge; }

	//傳回頂點'v'的第一個相鄰頂點
	int  first(int v) {
		for (int i = 0; i < numVertex; ++i)
			if (matrix[v][i] != 0)return i;
		return numVertex;     //代表這個點是孤立點
	}

	//傳回頂點v的下一個相鄰頂點（在頂點'w'之後）
	int next(int v, int w) {
		for (int i = w + 1; i < numVertex; ++i)
			if (matrix[v][i] != 0)return i;
		return numVertex;      //沒有下一個頂點
	}

	//設定邊的權重，i,j是頂點，wgt是邊的權重
	void setEdge(int i, int j, int wgt) {
		if (wgt <= 0)return;
		if (matrix[i][j] == 0)++numEdge;
		matrix[i][j] = wgt;
	}

	//删除邊，i,j是頂點
	void delEdge(int i, int j) {
		if (matrix[i][j] != 0)--numEdge;
		matrix[i][j] = 0;
	}

	//判斷邊是否在圖中，i,j是頂點,如果邊（i,j）權重不為0傳回true
	bool isEdge(int i, int j) {
		return matrix[i][j] != 0;
	}

	//傳回邊的權重，i,j是頂點，
	int weight(int i, int j) { return matrix[i][j]; }

	//擷取或者設定頂點'v'的标志值，友善确認這個頂點之前是否被我們通路過
	//val是要設定的值
	int getMark(int v) { return mark[v]; }
	void setMark(int v, int val) { mark[v] = val; }
};


           

三、時間複雜度

• 上面C++代碼 (和python的解法是完全一樣的) 的時間複雜度為 Θ ( ∣ V ∣ 2 + ∣ E ∣ ) = Θ ( ∣ V ∣ 2 ) \Theta(|V|^2+|E|)=\Theta(|V|^2) Θ(∣V∣2+∣E∣)=Θ(∣V∣2)
  • 說明：因為每次掃描需要進行 ∣ V ∣ |V| ∣V∣次（外層for循環），在整個外層for循環中，判斷并更新數組D需要進行 ∣ E ∣ |E| ∣E∣次，也就是每條邊都被通路有且僅有一次。在内層for循環中，查找minVertex需要 Θ ( ∣ V ∣ ) \Theta(|V|) Θ(∣V∣)的時間，是以總共需要 Θ ( ∣ V ∣ 2 + ∣ E ∣ ) \Theta(|V|^2+|E|) Θ(∣V∣2+∣E∣)的時間，又因為 ∣ E ∣ < ∣ V ∣ 2 |E|<|V|^2 ∣E∣<∣V∣2，故總的時間開銷是： Θ ( ∣ V ∣ 2 ) \Theta(|V|^2) Θ(∣V∣2)

四、用優先隊列優化

上面C++尋找minVertex的過程可以優化，下面代碼運作沒有問題，輸出結果和上面的一樣。時間複雜度是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)

• 說明：這種方法是把未處理的頂點按照距離值大小順序儲存在一個最小堆中，每次修改完D(w)的值後，将這個新的距離值和頂點作為一個新的元素添加到堆中。一個頂點目前在堆中的最小值會被優先找到，而其後的較大值将會被忽略，因為此時頂點已被标記為VISITED。
• 在最差情況下，堆中的元素數目會由 ∣ V ∣ |V| ∣V∣增加到 ∣ E ∣ |E| ∣E∣,這樣每次插入需要 O ( l o g 2 ∣ E ∣ ) O(log_2|E|) O(log2​∣E∣)的時間複雜度，雖然有兩層for循環，如果從邊的數目出發，會發現每條邊最多被通路一次，這樣總的時間複雜度是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣),至于那個do,while循環，它用的總時間也是 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)的，因為它每進行一次循環，都會移走一個頂點，最多有 ∣ E ∣ |E| ∣E∣個頂點，是以最多進行 ∣ E ∣ |E| ∣E∣次循環，而每次循環，裡面的 r e m o v e f i r s t ( ) removefirst() removefirst()的時間複雜度是 O ( l o g 2 ∣ E ∣ ) O(log_2|E|) O(log2​∣E∣)的，相乘，即得出 O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)，是以最終的時間複雜度是： O ( ∣ E ∣ l o g 2 ∣ E ∣ ) O(|E|log_2|E|) O(∣E∣log2​∣E∣)

/*程式代碼源于《資料結構與算法C++描述第三版》*/

class DijkElem {
public:
	int vertex, distance;
	DijkElem() { vertex = -1; distance = -1; }
	DijkElem(int v, int d) { vertex = v; distance = d; }
};
class DDComp {
public:
	static bool prior(DijkElem a, DijkElem b) {
		return (a.distance < b.distance);
	}
};

/*用優先隊列實作Dijkstra算法*/
void Dijkstra2(graph* G, int* D, int s) {
	/*v是目前的minVertex*/
	int i, v, w;
	DijkElem temp;
	DijkElem *E=new DijkElem[G->e()];
	temp.distance = 0;
	temp.vertex = s;
	E[0] = temp;
	heap<DijkElem, DDComp>H(E, 1, G->e());
	for (int i = 0; i < G->n(); ++i) {
		do {
			if (H.size() == 0)return;
			temp = H.removefirst();
			v = temp.vertex;
		} while (G->getMark(v) == VISITED);
		G->setMark(v, VISITED);
		if (D[v] == INF)return;    //說明節點v是孤立點，不可到達
		for(w=G->first(v);w<G->n();w=G->next(v,w))
			if (D[w] > D[v] + G->weight(v, w)) {
				D[w] = D[v] + G->weight(v, w);
				path[w] = v;
				temp.distance = D[w];
				temp.vertex = w;
				/*在最小堆中插入新的節點（距離）*/
				H.insert(temp);
			}
	}
	delete[]E;
}
           

上面的heap資料結構可以用C++ STL裡面的priority_queue，也可以自己寫一個最小堆，我用的是之前照着書上寫的最小堆代碼：

最小堆

heap.h

#pragma once
#include<assert.h>
#include<vector>
using namespace std;
template <typename E, typename Comp>
class heap
{
private:
	E* Heap;		//Pointer to the heap array
	int maxsize;	//Maximum size of the heap
	int n;			//Number of elements now in the heap
		//Helper function to put element in its correct place,and that moves the father node down
	void siftdown(int pos);
public:
	heap(E* h, int num, int max);
	int size()const;
	bool isLeaf(int pos)const;
	int leftchild(int pos)const;
	int rightchild(int pos)const;
	int parent(int pos)const;
	void buildHeap();
	void insert(const E& it);
	E removefirst();
	E remove(int pos);
};


//Swap two elements in the container
template<typename E>
void swap(E* array, int pos1, int pos2) {
	E temp = array[pos1];
	array[pos1] = array[pos2];
	array[pos2] = temp;
}

//Heap class
// E is the element in heap
//Comp is a class used to compare two elements
//Helper function to put element in its correct place,and that moves the father node down
template <typename E, typename Comp>
void heap<E, Comp>::siftdown(int pos) {
	while (!isLeaf(pos)) {//Stop if pos is a leaf
		int j = leftchild(pos);
		int rc = rightchild(pos);
		if ((rc < n) && Comp::prior(Heap[rc], Heap[j]))
			j = rc;		//Set j to greater child's value
		if (Comp::prior(Heap[pos], Heap[j]))
			return;	//Done
		swap(Heap, pos, j);
		pos = j;		//Move down
	}
}

/*
template<typename E, typename Comp>
E& heap<E, Comp>::operator[](int i) {
	assert(i < maxsize);	//Interrupt if i>=maxsize
	return E[i];
}
*/
template <typename E, typename Comp>
heap<E, Comp>::heap(E* h, int num, int max) {
	Heap = h;
	n = num;
	maxsize = max;
	buildHeap();
}
//Return current heap size
template <typename E, typename Comp>
int heap<E, Comp>::size()const {
	return n;
}
//True if pos is a leaf
template <typename E, typename Comp>
bool heap<E, Comp>::isLeaf(int pos)const {
	return ((pos >= n / 2) && (pos < n));
}
//Return leftchild position
template <typename E, typename Comp>
int heap<E, Comp>::leftchild(int pos)const {
	return 2 * pos + 1;
}
//Return rightchild position
template <typename E, typename Comp>
int heap<E, Comp>::rightchild(int pos)const {
	return 2 * pos + 2;
}
//Return parent position
template <typename E, typename Comp>
int heap<E, Comp>::parent(int pos)const {
	return (pos - 1) / 2;
}
//Heapify contents of Heap
template <typename E, typename Comp>
void heap<E, Comp>::buildHeap() {
	for (int i = n / 2 - 1; i >= 0; --i) {
		siftdown(i);
	}
}
//Insert "it" into the heap
template <typename E, typename Comp>
void heap<E, Comp>::insert(const E& it) {
	assert(n < maxsize);	//Terminate if heap is full
	int curr = n++;
	Heap[curr] = it;		//Start at end of heap
	//Move up until curr's parent > curr
	while ((curr != 0) && (Comp::prior(Heap[curr], Heap[parent(curr)]))) {
		swap(Heap, curr, parent(curr));
		curr = parent(curr);
	}
}

template <typename E, typename Comp>
E heap<E, Comp>::removefirst() {
	assert(n > 0);		//Interrupt if heap is empty
	swap(Heap, 0, --n);		//Swap first with last value.
	if (n != 0)siftdown(0);		//Siftdown new root val
	return Heap[n];			//Return deleted value
}

template <typename E, typename Comp>
E heap<E, Comp>::remove(int pos) {
	assert((pos >= 0) && (pos < n));  //Intertupt if it is in bad position
	if (pos == n - 1)n--;		//Last element,no work to do
	else {
		swap(Heap, pos, --n);		//Swap with last value
		while ((pos != 0) && (Comp::prior(Heap[pos], Heap[parent(pos)]))) {
			swap(Heap, pos, parent(pos));		//Push up large key
			pos = parent(pos);
		}
		if (n != 0)siftdown(pos);		//Push down small key
	}
	return Heap[n];
}