程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> C++用Dijkstra(迪傑斯特拉)算法求最短途徑

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

編輯:關於C++

C++用Dijkstra(迪傑斯特拉)算法求最短途徑。本站提示廣大學習愛好者:(C++用Dijkstra(迪傑斯特拉)算法求最短途徑)文章只能為提供參考,不一定能成為您想要的結果。以下是C++用Dijkstra(迪傑斯特拉)算法求最短途徑正文


算法引見

迪傑斯特拉算法是由荷蘭計算機迷信家狄克斯特拉於1959 年提出的,因而又叫狄克斯特拉算法。是從一個頂點到其他各頂點的最短途徑算法,處理的是有向圖中最短途徑問題。迪傑斯特拉算法次要特點是以起始點為中心向外層層擴展,直到擴展到起點為止。Dijkstra算法能得出最短途徑的最優解,但由於它遍歷計算的節點很多,所以效率低。

算法思想

按途徑長度遞增次第發生算法:

 把頂點集合V分紅兩組:

  (1)S:已求出的頂點的集合(初始時只含有源點V0)

  (2)V-S=T:尚未確定的頂點集合
  將T中頂點按遞增的次第參加到S中,保證:

  (1)從源點V0到S中其他各頂點的長度都不大於從V0到T中任何頂點的最短途徑長度

  (2)每個頂點對應一個間隔值

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

  T中頂點:從V0到此頂點的只包括S中頂點作兩頭頂點的最短途徑長度

  根據:可以證明V0到T中頂點Vk的,或是從V0到Vk的直接途徑的權值;或是從V0經S中頂點到Vk的途徑權值之和

使用舉例

(1)標題:編寫一個校園導游順序,為來訪的主人提供各種信息查詢服務。

    次要功用:1.設計學校的校園立體圖,所含景點不少於10個:頂點表示景點,邊表示途徑等;

         2.為主人提供圖中恣意景點相關信息的查詢;

         3.為主人提供圖中恣意景點的問路查詢,即查詢人以景點間的一條最短途徑。

      要求:1.設計一個主界面;

         2.設計功用菜單,供用戶選擇

         3.有一定的適用性。

(2)設計思緒:

  1、該題次要有算法思緒以及順序的邏輯思緒,首先從邏輯思緒講,進入順序,首先設計一個主菜單,選項有景點信息查詢,最短途徑查詢以及顯示景點的立體視圖三個子菜單,然後依據用戶的輸出選擇的子菜單前的編號,分進入不同的子菜單;該功用是由if….else if…. 語句完成。在景點信息查詢和最短途徑查詢子菜單下還有二級子菜 單,都是列 出一切景點並在後面編號,查詢景點信息時,輸出景點後面的編號即可,查詢最短途徑時,先輸出終點的編號,再輸出起點的編號。而顯示景點視圖則調用景點立體圖函數即可顯 示。

  2、算法思緒次要是迪傑斯特拉算法的思緒,應用迪傑斯特拉算法求最短途徑。

  3、先定義好圖的貯存構造,本題采用鄰接矩陣的方式來表示圖,並在主函數中初始化該圖;

  4、定義三個全局一維數組,一個bool類型數組S[]用來記載從v0到vi能否曾經確定了最短途徑,是則記S[i]=true ,否記S[i]= flase;一個int 類型數組Path[]用來記載從v0到vi的以後最短途徑上的vi的直接前驅頂點編號,若v 到vi之間有邊則記Path[i] = v的編號,否則記Path[i] = -1;最後一個數組D[]用來記載從v0到vi之間的最短途徑長度,存在則記v0到vi之間邊的權值或許權值和,否則記為MAX

  5、定義一個求最短途徑的函數,傳入的參數為圖和終點,首先停止初始化任務,初始化S[]數組全為false,D[]數組初始化為終點到各個頂點的權值,Path[]數組初始化為終點能否與各頂點有邊,有則記v0否則記-1;

  6、然後停止n-1次for循環,找出vo到其他n-1個頂點之間的最短途徑,比擬以後D[]數組中最小值,找到最小值的編號v,該編號就是從v0動身到一切頂點中間隔最短的頂點編號,然後把S[v]的值置為true。闡明從v0動身到頂點v曾經找到最短途徑;

  7、接著就要更新D[]數組,由於D[]數組是記載最短途徑的,如今曾經找到了一個頂點的最短途徑,已該頂點v為兩頭點,判別從該頂點v動身到剩下的頂點的途徑長度加上該點到v0的途徑長度能否小於直接從v0動身到其他頂點的途徑長度,假如小於,則更新D[i]為以該頂點v為兩頭點求得的途徑長度。更新Path[i] = v;即i的前驅不再是v0而是v;

  8、循環(6)(7)兩步n-1次即可失掉D[]數組,輸入D[]數組既是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能否曾經確定為最短途徑,確定了記true,否則記false
int Path[max]; //記載從源點V0到起點Vi的以後最短途徑上起點Vi的直接前驅頂點序號,若V0到Vi之間有邊前驅為V0否則為-1 
int D[max]; //記載源點到起點之間最短途徑的長度,存在記V0到Vi的邊的權值,否則記為MAX 
typedef struct
{
 string vexs[max]; //頂點表
 int arcs[max][max]; //鄰接矩陣 
 int vexnum, arcnum; //圖以後點數和邊數

}AMGraph;
//應用迪傑斯特拉算法求最短途徑
void ShortestPath_DIJ(AMGraph &G, int v0)
{//運用迪傑斯特拉算法求有向網G中的V0 定點到其他頂點的最短途徑
 int n = G.vexnum;//頂點數
 for (int v = 0; v < n; v++)//n個頂點順次初始化
 {
 S[v] = false;//S初始化為空集
 D[v] = G.arcs[v0][v];//將v0到各個起點的最短途徑長度初始化為邊上的權值
 if (D[v] < MAX)
  Path[v] = v0;//假如v0和v之間有邊,則將v的前驅初始化為v0
 else
  Path[v] = -1;//假如v0和v之間無邊,則將v的前驅初始化為-1
 }
 S[v0] = true; //將v0參加s
 D[v0] = 0;//源點到源點的權值為0
 //---------初始化完畢,開端主循環,每次求得v0到某個頂點的最短途徑,將v加到S數組
 for (int i = 1; i < n; i++)//順次對其他n-1個頂點停止計算
 {
 int min = MAX;
 int v = v0;
 for (int w = 0; w < n; w++)
 {
  if (!S[w] && D[w] < min)
  {//選擇一條以後最短途徑,起點為v
  v = w;
  min = D[w];
  }
  S[v] = true;//將v加到s集合中
  for (int w = 0; w < n; w++)
  {//更新從v0動身到集合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的前驅為v
  }
  }
 }
 }
}
//背景函數
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 ↘ 學院 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 << "|----------------------------鐵大導游小順序-----------------------|" << endl;
 cout << " |*********************************************************|" << endl;
 cout << " |--------------------1-景點信息查詢--------------|" << endl;
 cout << " |--------------------2-最短途徑查詢--------------|" << endl;
 cout << " |--------------------3-顯示景點視圖--------------|" << endl;
 cout << " |-------------------4-加入導游順序------ --------|" << endl;
 cout << "|*****************************************************************|" << endl;
 cout << ">>>請選擇:";
}
//景點信息查詢二級菜單
void jmenu()
{
 cout << "|*****************************************************************|" << endl;
 cout << " |-------------------------景點信息查詢------------------------|" << endl;
 cout << " |***********************************************************|" << endl;
 cout << " |----------------------1-信息學院引見-------------------| " << 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-信息學院-------------------| " << 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 = { { "信息學院","綜合餐廳","西操場","體育館","春晖樓",
   "基教", "九教", "九棟", "沁園", "翠園" },
 //-1代表兩邊不相連,權值有限大
 //鄰接矩陣 /* 信 綜 西 體 春 基 教 棟 沁 翠*/ 
   {{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)運轉截圖:

總結

以上就是關於C++用Dijkstra算法(迪傑斯特拉算法)求最短途徑的全部內容了,希望本文的內容對大家的學習或許任務帶來一定的協助,假如有疑問大家可以留言交流。

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved