|
一、最短路徑問題介紹 1、從圖中的某個頂點出發(fā)到達另外一個頂點的所經(jīng)過的邊的權(quán)重和最小的一條路徑，稱為最短路徑。 2、解決問題的算法： - 迪杰斯特拉算法（Dijkstra算法）
- 弗洛伊德算法（Floyd算法）
- SPFA算法
這篇文章，就先對Dijkstra算法來做一個詳細(xì)的介紹~ 二、Dijkstra算介紹迪科斯徹算法使用了廣度優(yōu)先搜索解決賦權(quán)有向圖或者無向圖的單源最短路徑問題，算法最終得到一個最短路徑樹。該算法常用于路由算法或者作為其他圖算法的一個子模塊。 Dijkstra算法采用的是一種貪心的策略，聲明一個數(shù)組dis來保存原點到各個頂點的最短距離和一個保存已經(jīng)找到了最短路徑的頂點的集合：T={}，初始時，原點 s 的路徑權(quán)重被賦為 0 （dis[s] = 0）。 若對于頂點 s 存在能直接到達的邊（s,m），則把dis[m]設(shè)為w（s, m）,同時把其他所有s不能直接到達的頂點的路徑長度設(shè)為無窮大。初始時，集合T只有頂點s。
然后，從dis數(shù)組選擇最小值，則該值就是原點s到該值對應(yīng)的頂點的最短路徑，并且把該點加入到T中，OK，此時完成一個頂點。
然后，我們需要看看新加入的頂點是否可以到達其他頂點并且看看通過該頂點到達其他點的路徑長度是否比源點直接到達短，如果是，那么就替換這些頂點在dis中的值。
然后，又從dis中找出最小值，重復(fù)上述動作，直到T中包含了圖的所有頂點。 三、Dijkstra算法示例演示以下圖為例，找出從頂點v1到其他各個頂點的最短路徑。 首先第一步，我們先聲明一個dis數(shù)組，該數(shù)組初始化（原頂點v1到其它點的直接距離，無法直達則記為無窮）的值為：
我們的頂點集合T的初始化為：T={v1} 既然是求 v1頂點到其余各個頂點的最短路程，那就先找一個離第一個頂點 v1最近的頂點。通過數(shù)組 dis 可知當(dāng)前離v1頂點最近是 v3頂點。當(dāng)選擇了第二個頂點v3后，dis[2]（索引從0開始，即v1到v3的最短距離）的值就已經(jīng)從“估計值”變?yōu)榱恕按_定值”，即 v1頂點到 v3頂點的最短路程就是當(dāng)前 dis[2]值。將v3加入到T中。 提示：因為目前離 v1頂點最近的是 v3頂點，并且這個圖所有的邊都是正數(shù)，那么肯定不可能通過第三個頂點中轉(zhuǎn)，使得 v1頂點到 v3頂點的路程進一步縮短了。因為 v1頂點到其它頂點的路程肯定沒有 v1到 v3頂點短。 OK，既然確定了一個頂點的最短路徑，下面我們就要根據(jù)這個新入的頂點v3會有出度（即v3可達到的路徑），發(fā)現(xiàn)以v3 為弧尾的有：< v3,v4 >,那么我們看看路徑：v1–v3–v4的長度是否比v1–v4短，其實這個已經(jīng)是很明顯的了，因為dis[3]代表的就是v1–v4的長度為無窮大，而v1–v3–v4的長度為：10+50=60，dis[3]要更新為 60, 得到如下結(jié)果：
此時，頂點集合： T={v1, v3} 然后，我們又從除dis[2]和dis[0]外的其他值中尋找最小值，發(fā)現(xiàn)dis[4]（即v1到v5的直達距離）的值最小，通過之前是解釋的原理，可以知道v1到v5的最短距離就是dis[4]的值，然后，我們把v5加入到集合T中，然后，考慮v5的出度是否會影響我們的數(shù)組dis的值，v5有兩條出度：< v5,v4>和 < v5,v6>,然后我們發(fā)現(xiàn)：v1–v5–v4的長度為：50，而dis[3]的值為60，所以我們要更新dis[3]的值.另外，v1-v5-v6的長度為：90，而dis[5]為100，所以我們需要更新dis[5]的值。更新后的dis數(shù)組如下圖：
此時，頂點集合： T={v1, v3, v5} 然后，繼續(xù)從dis中選擇未確定的頂點的值中選擇一個最小的值，發(fā)現(xiàn)dis[3]的值是最小的，所以把v4加入到集合T中，此時集合T={v1,v3,v5,v4},然后，考慮v4的出度是否會影響我們的數(shù)組dis的值，v4有一條出度：< v4,v6>,然后我們發(fā)現(xiàn)：v1–v5–v4–v6的長度為：60，而dis[5]的值為90，所以我們要更新dis[5]的值，更新后的dis數(shù)組如下圖：
此時，頂點集合： T={v1, v3, v5, v4} 然后，我們使用同樣原理，分別確定了v6和v2的最短路徑，最后dis的數(shù)組的值如下：
最后，頂點集合： T={v1, v3, v5, v4, v6, v2} 因此，從圖中，我們可以發(fā)現(xiàn)v1-v2的值為：∞，代表沒有路徑從v1到達v2。所以我們得到的最后的結(jié)果為： 四、Dijkstra算法的代碼實現(xiàn)（c++）代碼語言：javascript 代碼運行次數(shù)：0 代碼語言：javascript 代碼運行次數(shù)：0 /************************************************************//* 程序作者：Willam *//************************************************************///@盡量寫出完美的程序
#include<iostream>#include<string>using namespace std;
/*本程序是使用Dijkstra算法實現(xiàn)求解最短路徑的問題采用的鄰接矩陣來存儲圖*///記錄起點到每個頂點的最短路徑的信息struct Dis { string path; int value; bool visit; Dis() { visit = false; value = 0; path = ""; }};
class Graph_DG {private: int vexnum; //圖的頂點個數(shù) int edge; //圖的邊數(shù) int **arc; //鄰接矩陣 Dis * dis; //記錄各個頂點最短路徑的信息public: //構(gòu)造函數(shù) Graph_DG(int vexnum, int edge); //析構(gòu)函數(shù) ~Graph_DG(); // 判斷我們每次輸入的的邊的信息是否合法 //頂點從1開始編號 bool check_edge_value(int start, int end, int weight); //創(chuàng)建圖 void createGraph(); //打印鄰接矩陣 void print(); //求最短路徑 void Dijkstra(int begin); //打印最短路徑 void print_path(int);};
代碼語言：javascript 代碼運行次數(shù)：0 #include"Dijkstra.h"
//構(gòu)造函數(shù)Graph_DG::Graph_DG(int vexnum, int edge) { //初始化頂點數(shù)和邊數(shù) this->vexnum = vexnum; this->edge = edge; //為鄰接矩陣開辟空間和賦初值 arc = new int*[this->vexnum]; dis = new Dis[this->vexnum]; for (int i = 0; i < this->vexnum; i++) { arc[i] = new int[this->vexnum]; for (int k = 0; k < this->vexnum; k++) { //鄰接矩陣初始化為無窮大 arc[i][k] = INT_MAX; } }}//析構(gòu)函數(shù)Graph_DG::~Graph_DG() { delete[] dis; for (int i = 0; i < this->vexnum; i++) { delete this->arc[i]; } delete arc;}
// 判斷我們每次輸入的的邊的信息是否合法//頂點從1開始編號bool Graph_DG::check_edge_value(int start, int end, int weight) { if (start<1 || end<1 || start>vexnum || end>vexnum || weight < 0) { return false; } return true;}
void Graph_DG::createGraph() { cout << "請輸入每條邊的起點和終點（頂點編號從1開始）以及其權(quán)重" << endl; int start; int end; int weight; int count = 0; while (count != this->edge) { cin >> start >> end >> weight; //首先判斷邊的信息是否合法 while (!this->check_edge_value(start, end, weight)) { cout << "輸入的邊的信息不合法，請重新輸入" << endl; cin >> start >> end >> weight; } //對鄰接矩陣對應(yīng)上的點賦值 arc[start - 1][end - 1] = weight; //無向圖添加上這行代碼 //arc[end - 1][start - 1] = weight; ++count; }}
void Graph_DG::print() { cout << "圖的鄰接矩陣為：" << endl; int count_row = 0; //打印行的標(biāo)簽 int count_col = 0; //打印列的標(biāo)簽 //開始打印 while (count_row != this->vexnum) { count_col = 0; while (count_col != this->vexnum) { if (arc[count_row][count_col] == INT_MAX) cout << "∞" << " "; else cout << arc[count_row][count_col] << " "; ++count_col; } cout << endl; ++count_row; }}void Graph_DG::Dijkstra(int begin){ //首先初始化我們的dis數(shù)組 int i; for (i = 0; i < this->vexnum; i++) { //設(shè)置當(dāng)前的路徑 dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1); dis[i].value = arc[begin - 1][i]; } //設(shè)置起點的到起點的路徑為0 dis[begin - 1].value = 0; dis[begin - 1].visit = true;
int count = 1; //計算剩余的頂點的最短路徑（剩余this->vexnum-1個頂點） while (count != this->vexnum) { //temp用于保存當(dāng)前dis數(shù)組中最小的那個下標(biāo) //min記錄的當(dāng)前的最小值 int temp=0; int min = INT_MAX; for (i = 0; i < this->vexnum; i++) { if (!dis[i].visit && dis[i].value<min) { min = dis[i].value; temp = i; } } //cout << temp + 1 << " "<<min << endl; //把temp對應(yīng)的頂點加入到已經(jīng)找到的最短路徑的集合中 dis[temp].visit = true; ++count; for (i = 0; i < this->vexnum; i++) { //注意這里的條件arc[temp][i]!=INT_MAX必須加，不然會出現(xiàn)溢出，從而造成程序異常 if (!dis[i].visit && arc[temp][i]!=INT_MAX && (dis[temp].value + arc[temp][i]) < dis[i].value) { //如果新得到的邊可以影響其他為訪問的頂點，那就就更新它的最短路徑和長度 dis[i].value = dis[temp].value + arc[temp][i]; dis[i].path = dis[temp].path + "-->v" + to_string(i + 1); } } }
}void Graph_DG::print_path(int begin) { string str; str = "v" + to_string(begin); cout << "以"<<str<<"為起點的圖的最短路徑為：" << endl; for (int i = 0; i != this->vexnum; i++) { if(dis[i].value!=INT_MAX) cout << dis[i].path << "=" << dis[i].value << endl; else { cout << dis[i].path << "是無最短路徑的" << endl; } }}
代碼語言：javascript 代碼運行次數(shù)：0 #include"Dijkstra.h"
//檢驗輸入邊數(shù)和頂點數(shù)的值是否有效，可以自己推算為啥：//頂點數(shù)和邊數(shù)的關(guān)系是：((Vexnum*(Vexnum - 1)) / 2) < edgebool check(int Vexnum, int edge) { if (Vexnum <= 0 || edge <= 0 || ((Vexnum*(Vexnum - 1)) / 2) < edge) return false; return true;}int main() { int vexnum; int edge;
cout << "輸入圖的頂點個數(shù)和邊的條數(shù)：" << endl; cin >> vexnum >> edge; while (!check(vexnum, edge)) { cout << "輸入的數(shù)值不合法，請重新輸入" << endl; cin >> vexnum >> edge; } Graph_DG graph(vexnum, edge); graph.createGraph(); graph.print(); graph.Dijkstra(1); graph.print_path(1); system("pause"); return 0;}
輸入：
代碼語言：javascript 代碼運行次數(shù)：0 6 81 3 101 5 301 6 1002 3 53 4 504 6 105 6 605 4 20
代碼語言：javascript 代碼運行次數(shù)：0 從輸出可以看出，程序的結(jié)果和我們之前手動計算的結(jié)果是一樣的。
|
