C++用Dijkstra(迪杰斯特拉)算法求最短路徑

更新時間：2016年12月14日 11:28:11 投稿：daisy

Dijkstra（迪杰斯特拉）算法是典型的最短路徑路由算法，用于計算一個節(jié)點到其他所有節(jié)點的最短路徑。主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。下面這篇文章就給大家介紹關(guān)于C++用Dijkstra算法(迪杰斯特拉算法)求最短路徑的方法，下面來一起看看吧。

算法介紹

迪杰斯特拉算法是由荷蘭計算機(jī)科學(xué)家狄克斯特拉于1959 年提出的，因此又叫狄克斯特拉算法。是從一個頂點到其余各頂點的最短路徑算法，解決的是有向圖中最短路徑問題。迪杰斯特拉算法主要特點是以起始點為中心向外層層擴(kuò)展，直到擴(kuò)展到終點為止。Dijkstra算法能得出最短路徑的最優(yōu)解，但由于它遍歷計算的節(jié)點很多，所以效率低。

算法思想

按路徑長度遞增次序產(chǎn)生算法：

　把頂點集合V分成兩組：

　?。?）S：已求出的頂點的集合（初始時只含有源點V0）

　?。?）V-S=T：尚未確定的頂點集合
　　將T中頂點按遞增的次序加入到S中，保證：

　?。?）從源點V0到S中其他各頂點的長度都不大于從V0到T中任何頂點的最短路徑長度

　　（2）每個頂點對應(yīng)一個距離值

　　S中頂點：從V0到此頂點的長度

　　T中頂點：從V0到此頂點的只包括S中頂點作中間頂點的最短路徑長度

　　依據(jù)：可以證明V0到T中頂點Vk的，或是從V0到Vk的直接路徑的權(quán)值；或是從V0經(jīng)S中頂點到Vk的路徑權(quán)值之和

應(yīng)用舉例

（1）題目：編寫一個校園導(dǎo)游程序，為來訪的客人提供各種信息查詢服務(wù)。

　　　　主要功能：1.設(shè)計學(xué)校的校園平面圖，所含景點不少于10個：頂點表示景點，邊表示路徑等；

　　　　　　　　　2.為客人提供圖中任意景點相關(guān)信息的查詢；

　　　　　　　　　3.為客人提供圖中任意景點的問路查詢，即查詢?nèi)艘跃包c間的一條最短路徑。

　　　　　　要求：1.設(shè)計一個主界面；

　　　　　　 2.設(shè)計功能菜單，供用戶選擇

　　　　　　 3.有一定的實用性。

（2）設(shè)計思路：

　　1、該題主要有算法思路以及程序的邏輯思路，首先從邏輯思路講，進(jìn)入程序，首先設(shè)計一個主菜單，選項有景點信息查詢，最短路徑查詢以及顯示景點的平面視圖三個子菜單，然后根據(jù)用戶的輸入選擇的子菜單前的編號，分進(jìn)入不同的子菜單；該功能是由if….else if…. 語句實現(xiàn)。在景點信息查詢和最短路徑查詢子菜單下還有二級子菜　單，都是列出所有景點并在前面編號，查詢景點信息時，輸入景點前面的編號即可，查詢最短路徑時，先輸入起點的編號，再輸入終點的編號。而顯示景點視圖則調(diào)用景點平面圖函數(shù)即可顯示。

　　2、算法思路主要是迪杰斯特拉算法的思路，利用迪杰斯特拉算法求最短路徑。

　　3、先定義好圖的儲存結(jié)構(gòu)，本題采用鄰接矩陣的方式來表示圖，并在主函數(shù)中初始化該圖；

　　4、定義三個全局一維數(shù)組，一個bool類型數(shù)組S[]用來記錄從v0到vi是否已經(jīng)確定了最短路徑，是則記S[i]=true ,否記S[i]= flase；一個int 類型數(shù)組Path[]用來記錄從v0到vi的當(dāng)前最短路徑上的vi的直接前驅(qū)頂點編號，若v 到vi之間有邊則記Path[i] = v的編號，否則記Path[i] = -1；最后一個數(shù)組D[]用來記錄從v0到vi之間的最短路徑長度，存在則記v0到vi之間邊的權(quán)值或者權(quán)值和，否則記為MAX

　　5、定義一個求最短路徑的函數(shù)，傳入的參數(shù)為圖和起點，首先進(jìn)行初始化工作，初始化S[]數(shù)組全為false，D[]數(shù)組初始化為起點到各個頂點的權(quán)值，Path[]數(shù)組初始化為起點是否與各頂點有邊，有則記v0否則記-1；

　　6、然后進(jìn)行n-1次for循環(huán)，找出vo到其余n-1個頂點之間的最短路徑，比較當(dāng)前D[]數(shù)組中最小值，找到最小值的編號v，該編號就是從v0出發(fā)到所有頂點中距離最短的頂點編號，然后把S[v]的值置為true。說明從v0出發(fā)到頂點v已經(jīng)找到最短路徑；

　　7、接著就要更新D[]數(shù)組，因為D[]數(shù)組是記錄最短路徑的，現(xiàn)在已經(jīng)找到了一個頂點的最短路徑，已該頂點v為中間點，判斷從該頂點v出發(fā)到剩下的頂點的路徑長度加上該點到v0的路徑長度是否小于直接從v0出發(fā)到其余頂點的路徑長度，如果小于，則更新D[i]為以該頂點v為中間點求得的路徑長度。更新Path[i] = v；即i的前驅(qū)不再是v0而是v;

　　8、循環(huán)（6）（7）兩步n-1次即可得到D[]數(shù)組，輸出D[]數(shù)組既是v0到所有頂點的最短路徑長度；

（3）源代碼：

#include<iostream>
#include<fstream>
#include<string>
using namespace std;
/**
 *作者：Dmego
 *時間：2016-12-12
 */
#define MAX 1000000 //表示極大值∞
#define max 10
bool S[max]; //記錄從源點V0到終點Vi是否已經(jīng)確定為最短路徑，確定了記true，否則記false
int Path[max]; //記錄從源點V0到終點Vi的當(dāng)前最短路徑上終點Vi的直接前驅(qū)頂點序號，若V0到Vi之間有邊前驅(qū)為V0否則為-1 
int D[max]; //記錄源點到終點之間最短路徑的長度，存在記V0到Vi的邊的權(quán)值，否則記為MAX 
typedef struct
{
 string vexs[max]; //頂點表
 int arcs[max][max]; //鄰接矩陣 
 int vexnum, arcnum; //圖當(dāng)前點數(shù)和邊數(shù)

}AMGraph;
//利用迪杰斯特拉算法求最短路徑
void ShortestPath_DIJ(AMGraph &G, int v0)
{//使用迪杰斯特拉算法求有向網(wǎng)G中的V0 定點到其余頂點的最短路徑
 int n = G.vexnum;//頂點數(shù)
 for (int v = 0; v < n; v++)//n個頂點依次初始化
 {
 S[v] = false;//S初始化為空集
 D[v] = G.arcs[v0][v];//將v0到各個終點的最短路徑長度初始化為邊上的權(quán)值
 if (D[v] < MAX)
  Path[v] = v0;//如果v0和v之間有邊，則將v的前驅(qū)初始化為v0
 else
  Path[v] = -1;//如果v0和v之間無邊，則將v的前驅(qū)初始化為-1
 }
 S[v0] = true; //將v0加入s
 D[v0] = 0;//源點到源點的權(quán)值為0
 //---------初始化結(jié)束，開始主循環(huán)，每次求得v0到某個頂點的最短路徑，將v加到S數(shù)組
 for (int i = 1; i < n; i++)//依次對其余n-1個頂點進(jìn)行計算
 {
 int min = MAX;
 int v = v0;
 for (int w = 0; w < n; w++)
 {
  if (!S[w] && D[w] < min)
  {//選擇一條當(dāng)前最短路徑，終點為v
  v = w;
  min = D[w];
  }
  S[v] = true;//將v加到s集合中
  for (int w = 0; w < n; w++)
  {//更新從v0出發(fā)到集合V-S上所有頂點的最短路徑長度
  if (!S[w] && (D[v] + G.arcs[v][w] < D[w]))
  {
   D[w] = D[v] + G.arcs[v][w];//更新D[w]
   Path[w] = v;//更改w的前驅(qū)為v
  }
  }
 }
 }
}
//背景函數(shù)
void backGround()
{
 cout << "|*****************************************************************|" << endl;
 cout << " |------------------------鐵大旅游景點圖-----------------|" << endl;
 cout << "|*****************************************************************|" << endl;
 cout << "|  ⑦      單位：米 |" << endl;
 cout << "|  九教       |" << endl;
 cout << "|  ◎     ⑧  |" << endl;
 cout << "|  ↗↖     九棟  |" << endl;
 cout << "| ③ 200╱ ╲     ◎  |" << endl;
 cout << "| 西 ↙ ╲ 150    ↗ ↖  |" << endl;
 cout << "| 操 ◎  ╲ ①  160 ╱ ╲ 200 |" << endl;
 cout << "| 場 ↖150  ╲ 信息  ⑥ ╱  ╲ |" << endl;
 cout << "| ④ ↘ 140 ↘ 學(xué)院 200 基教 ↙ 230 ↘ |" << endl;
 cout << "| 體育館 ◎-------------→◎←--------------→◎←--------------→◎ |" << endl;
 cout << "|  ↖  ↗ ↖  ↗ ↖  ↗② |" << endl;
 cout << "|  100 ╲ ╱ ╲ 125 ╱ ╲ 150 ╱ 綜 |" << endl;
 cout << "|  ↘ ↙ 100 ╲ ╱135 ╲ ╱145 餐 |" << endl;
 cout << "|   ◎  ↘ ↙  ↘ ↙ |" << endl;
 cout << "|  ⑨ 沁園  ◎   ◎  |" << endl;
 cout << "|    ⑩ 翠園  ⑤ 春暉樓  |" << endl;
 cout << "|        |" << endl;
 cout << "|*****************************************************************|" << endl;

}
//主菜單
void menu()
{
 cout << "|*****************************************************************|" << endl;
 cout << "|----------------------------鐵大導(dǎo)游小程序-----------------------|" << endl;
 cout << " |*********************************************************|" << endl;
 cout << " |--------------------1-景點信息查詢--------------|" << endl;
 cout << " |--------------------2-最短路徑查詢--------------|" << endl;
 cout << " |--------------------3-顯示景點視圖--------------|" << endl;
 cout << " |-------------------4-退出導(dǎo)游程序------ --------|" << endl;
 cout << "|*****************************************************************|" << endl;
 cout << ">>>請選擇：";
}
//景點信息查詢二級菜單
void jmenu()
{
 cout << "|*****************************************************************|" << endl;
 cout << " |-------------------------景點信息查詢------------------------|" << endl;
 cout << " |***********************************************************|" << endl;
 cout << " |----------------------1-信息學(xué)院介紹-------------------| " << endl;
 cout << " |----------------------2-綜合餐廳介紹-------------------| " << endl;
 cout << " |----------------------3-西操場介紹---------------------| " << endl;
 cout << " |----------------------4-體育館介紹---------------------| " << endl;
 cout << " |----------------------5-春暉樓介紹---------------------| " << endl;
 cout << " |----------------------6-基教介紹-----------------------| " << endl;
 cout << " |----------------------7-九教介紹-----------------------| " << endl;
 cout << " |----------------------8-九棟介紹-----------------------| " << endl;
 cout << " |----------------------9-沁園介紹-----------------------| " << endl;
 cout << " |---------------------10-翠園介紹-----------------------| " << endl;
 cout << "|*****************************************************************|" << endl;
 cout << ">>>請要查詢的景點編號：";
}
//最短路徑查詢二級菜單
void pmenu()
{
 cout << "|*****************************************************************|" << endl;
 cout << " |-------------------------最短路徑查詢------------------------|" << endl;
 cout << " |***********************************************************|" << endl;
 cout << " |---------------------1-信息學(xué)院-------------------| " << endl;
 cout << " | --------------------2-綜合餐廳-------------------| " << endl;
 cout << " |---------------------3-西操場---------------------| " << endl;
 cout << " |---------------------4-體育館---------------------| " << endl;
 cout << " |---------------------5-春暉樓---------------------| " << endl;
 cout << " |---------------------6-基教-----------------------| " << endl;
 cout << " |---------------------7-九教-----------------------| " << endl;
 cout << " |---------------------8-九棟-----------------------| " << endl;
 cout << " |---------------------9-沁園-----------------------| " << endl;
 cout << " |--------------------10-翠園-----------------------| " << endl;
 cout << "|*****************************************************************|" << endl;
 cout << ">>>請依次輸入起點編號和終點編號：";
}
void main()
{
 //初始化操作
 AMGraph amg = { { "信息學(xué)院","綜合餐廳","西操場","體育館","春暉樓",
   "基教", "九教", "九棟", "沁園", "翠園" },
 //-1代表兩邊不相連，權(quán)值無限大
 //鄰接矩陣 /* 信 綜 西 體 春 基 教 棟 沁 翠*/ 
   {{MAX,MAX,MAX,140,MAX,200,150,MAX,100,125 },
   {MAX,MAX,MAX,MAX,145,230,MAX,100,MAX,MAX },
   {MAX,MAX,MAX,150,MAX,MAX,200,MAX,MAX,MAX },
   {140,MAX,150,MAX,MAX,MAX,MAX,MAX,100,MAX },
   {MAX,145,MAX,MAX,MAX,150,MAX,MAX,MAX,MAX },
   {200,230,MAX,MAX,150,MAX,MAX,160,MAX,135 },
   {150,MAX,200,MAX,MAX,MAX,MAX,MAX,MAX,MAX },
   {MAX,200,MAX,MAX,MAX,160,MAX,MAX,MAX,MAX },
   {100,MAX,MAX,100,MAX,MAX,MAX,MAX,MAX,MAX },
   {125,MAX,MAX,MAX,MAX,135,MAX,MAX,MAX,MAX }
   },10,14};
 int f, ff;
 int start, end;
 while (true)
 {
 cout << endl;
 menu();
 cin >> f;
 if (f == 1)
 {
  jmenu();
  cin >> ff;
　　　　　　　//景點信息從文件中讀取
  ifstream outfile("schooltravel.txt", ios :: out | ios :: binary);
  if (!outfile)
  {
  cerr << "讀取景點介紹文件失?。? << endl;
  abort();
  }
  string str[max];
  int i = 0;
  while (getline(outfile, str[i++]));
  cout << "|-----------------------景點介紹-------------------| " << endl;
  if (ff == 1)
  cout << str[0] << endl;
  else if (ff == 2)
  cout << str[1] << endl;
  else if (ff == 3)
  cout << str[2] << endl;
  else if(ff == 4)
  cout << str[3] << endl;
  else if (ff == 5)
  cout << str[4] << endl;
  else if (ff == 6)
  cout << str[5] << endl;
  else if (ff == 7)
  cout << str[6] << endl;
  else if (ff == 8)
  cout << str[7] << endl;
  else if (ff == 9)
  cout << str[8] << endl;
  else if (ff == 10)
  cout << str[9] << endl;
  cout << "|-------------------------------------------------|" << endl;
 }
 else if (f == 2)
 {
  pmenu();
  cin >> start >> end;
  ShortestPath_DIJ(amg, start - 1);
  int temp = end-1;
  int temp1, temp2;
  int flag[max], m = 0;
  cout << "從" << amg.vexs[start - 1] << "到" << amg.vexs[end - 1] << "最短路徑為：" ;
  while (temp!= -1)
  {
  flag[m++] = temp;
  temp1 = temp ;
  temp2 = Path[temp1];
  temp = temp2;
  }
  for (int i = m-1; i >= 0; i--)
  {
  cout <<amg.vexs[flag[i]] << "->";
  }
  cout << endl;
  cout << "最短路徑值為：" << D[end - 1] <<"米"<< endl;
 }
 else if (f == 3)
 {
  backGround();
 }
 else if (f == 4)
 {
  cout << ">>>退出成功！" << endl;
  exit(0);
 }
 }
}

（4）運行截圖：