先上圖：

現在要找到地點V1到其余各個地點的最短路徑（圖中數字的單位默認為km.）。有一個原則是：永遠找最小，確保無更小。

第一步：v1->v1,v1->v2,...v1->v7的距離用一維數組dis[0],dis[1],dis[2],...dis[6]表示。初始化數組：dis=[0 50 inf inf 30 inf inf];

第二步：找到dis數組中的最小值(注意不算v1->v1=0)，它是dis[4]=30;這個距離就是v1->v5的最小距離了，因為所有的距離都是正數，如果你從v1出發，通過其他頂點繞路繞到v5,那總距離肯定大于30，因為30+（一個大于0的數）肯定大于30.此時，找到了v1->v5的最短路徑；

第三步：把頂點v5置為true,代表頂點v5已被訪問；

第四步：看v5通往里，從圖上可以看到v5通往v3和v7,v5->v3的距離是60，v5->v7的距離是120，所以通過v5中轉到v3和v7后，v1->v3的距離變成30+60=90，v1->v7的距離變成30+120=150；這對dis數組中保存的v1到其它各個頂點的距離產生了影響， 此時就用更小的值去更新dis數組中的值。更新后的dis數組是：dis=[0 50 90 inf 30 inf 150].(注：inf代表無窮大)

第五步：找dis數組中除去v1->v5=30這個值之后的最小值，它是v1->v2=50，找到后把頂點v2置為ture.

第六步：從v1出發，通過v2中轉，看v2會到達哪里。可以看到，v2->v3=20,這時更新dis數組中v1->v3值，把90更新成70.此時數組dis=[0 50 70 inf 30 inf 150].

第七步：重復第5步，找排除掉頂點是ture的值后，剩余的數的最小值，它是v1->v3=70，把頂點v3置為true.

第八步：從v1出發，通過v3中轉，看v3會到達哪里。可以看到，v3->v7=10,這時更新dis數組中v1->v7值，把150更新成80.此時數組dis=[0 50 70 inf 30 inf 80].

第九步：結束！

最終結果：

?

以下C++代碼來源于：https://blog.csdn.net/qq_35644234/article/details/60870719

?Dijkstra.h文件的代碼：

/************************************************************/ /* 程序作者：Willam */ /* 程序完成時間：2017/3/8 */ /* 有任何問題請聯系：2930526477@qq.com */ /************************************************************/ //@盡量寫出完美的程序#pragma once //#pragma once是一個比較常用的C/C++雜注， //只要在頭文件的最開始加入這條雜注， //就能夠保證頭文件只被編譯一次。 #include<iostream> #include<string> using namespace std;/* 本程序是使用Dijkstra算法實現求解最短路徑的問題 采用的鄰接矩陣來存儲圖 */ //記錄起點到每個頂點的最短路徑的信息 struct Dis {string path;int value;bool visit;Dis() {visit = false;value = 0;path = "";} };class Graph_DG { private:int vexnum; //圖的頂點個數int edge; //圖的邊數int **arc; //鄰接矩陣Dis * dis; //記錄各個頂點最短路徑的信息 public://構造函數Graph_DG(int vexnum, int edge);//析構函數~Graph_DG();// 判斷我們每次輸入的的邊的信息是否合法//頂點從1開始編號bool check_edge_value(int start, int end, int weight);//創建圖void createGraph();//打印鄰接矩陣void print();//求最短路徑void Dijkstra(int begin);//打印最短路徑void print_path(int); }; View Code

Dijkstra.cpp文件的代碼：

#include"Dijkstra.h"//構造函數 Graph_DG::Graph_DG(int vexnum, int edge) {//初始化頂點數和邊數this->vexnum = vexnum;//this 代表調用構造函數的那一個一個對象的地址this->edge = edge;//為鄰接矩陣開辟空間和賦初值arc = new int*[this->vexnum];//arc 是二級指針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;}} } //析構函數 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開始）以及其權重" << 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;}//對鄰接矩陣對應上的點賦值arc[start - 1][end - 1] = weight;//無向圖添加上這行代碼//arc[end - 1][start - 1] = weight;++count;} }void Graph_DG::print() {cout << "圖的鄰接矩陣為：" << endl;int count_row = 0; //打印行的標簽int count_col = 0; //打印列的標簽//開始打印while (count_row != this->vexnum) {count_col = 0;while (count_col != this->vexnum) {if (arc[count_row][count_col] == INT_MAX)cout << "∞" << " ";elsecout << arc[count_row][count_col] << " ";++count_col;}cout << endl;++count_row;} } void Graph_DG::Dijkstra(int begin){//首先初始化我們的dis數組int i;for (i = 0; i < this->vexnum; i++) {//設置當前的路徑dis[i].path = "v" + to_string(begin) + "-->v" + to_string(i + 1);dis[i].value = arc[begin - 1][i];}//設置起點的到起點的路徑為0dis[begin - 1].value = 0;dis[begin - 1].visit = true;int count = 1;//計算剩余的頂點的最短路徑（剩余this->vexnum-1個頂點）while (count != this->vexnum) {//temp用于保存當前dis數組中最小的那個下標//min記錄的當前的最小值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對應的頂點加入到已經找到的最短路徑的集合中dis[temp].visit = true;++count;for (i = 0; i < this->vexnum; i++) {//注意這里的條件arc[temp][i]!=INT_MAX必須加，不然會出現溢出，從而造成程序異常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;}} } View Code

main.cpp文件的代碼：

#include"Dijkstra.h"//檢驗輸入邊數和頂點數的值是否有效，可以自己推算為啥： //頂點數和邊數的關系是：((Vexnum*(Vexnum - 1)) / 2) < edge bool 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 << "輸入圖的頂點個數和邊的條數：" << endl;cin >> vexnum >> edge;while (!check(vexnum, edge)) {cout << "輸入的數值不合法，請重新輸入" << endl;cin >> vexnum >> edge;}Graph_DG graph(vexnum, edge);graph.createGraph();graph.print();graph.Dijkstra(1);graph.print_path(1);system("pause");return 0; } View Code

運行結果：

?

---

?

轉載于:https://www.cnblogs.com/yibeimingyue/p/9998360.html

總結

以上是生活随笔為你收集整理的最短路径问题----Dijkstra算法的解释的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。