dijkstra算法詳細分析

// dijkstra.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

//狄傑斯特拉算法尋找圖中的最短距離//

#include <iostream>

#include "stdio.h"

#include "stdlib.h"

#include <deque>

#include <vector>

#include <algorithm>

using namespace std;

 //資料元素最大個數//

  const int maxnum =100; 

 //定義無窮大用來初始化特殊路徑數組;表示s中的點沒有能夠連結到此點。

  const int maxint =999999;

  //各個數組都是從下标1開始的

  int dist1[maxnum];     //用來存貯目前點到源點的距離//

  int prev1[maxnum];     //記錄目前點的前一個節點；

  int c1[maxnum][maxnum];//記錄圖的兩點間路徑的長度；

  int n1,line1;           //圖的節點數和路徑數//

  void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum]);

  void initGraph(string path);

  void searchPath(int *prev,int v, int u);

int _tmain(int argc, _TCHAR* argv[])

{

//初始化圖

 initGraph("input.txt");

//狄傑斯特拉算法進行最短距離計算//

 dijkstra(n1,1,dist1,prev1,c1);

 //輸出元點到各個點的最短距離；

 searchPath(prev1,1,n1);

//輸出；

return 0;

}

         //函數名: freopen

//功 能: 替換一個流，或者說重新配置設定檔案指針，實作重定向。如果stream流已經打開，則先關閉該流。如果該流已經定向，則freopen将會清除該定向。此函數一般用于将一個指定的檔案打開一個預定義的流：标準輸入、标準輸出或者标準出錯。

//用 法: FILE *freopen(const char *filename,const char *type, FILE *stream);

         //頭檔案：stdio.h

//傳回值：如果成功則傳回該指向該stream的指針,否則為NULL//

   void initGraph(string path)

   {

     freopen(path.c_str(),"r",stdin);

//輸入點數//

cin>>n1;

// 輸入路徑數；

cin>>line1;

int p,q,len;

 //初始化為最大整數//

for (int i=1;i<=n1;i++)

{

for (int j=1;j<=n1;j++)

{

c1[i][j]=maxint;

}

}

//輸入點和邊

for (int i=1;i<=line1;i++)

{

cin>>p>>q>>len;

if (len<c1[p][q])//有重邊

{

c1[p][q]=len;//p指向q

c1[q][p]=len;//q指向p;表示無向圖；

}

}

//初始化目前距離數組為最大整數值

for (int i=1;i<=n1;i++)

{

dist1[i]=maxint;

}

//輸出到螢幕所輸入的結果；

for(int i=1; i<=n1; ++i)

{

for(int j=1; j<=n1; ++j)

printf("%9d", c1[i][j]);

printf("\n");

}

   }

   // n -- n nodes

   // v -- the source node

   // dist[] -- the distance from the ith node to the source node

   // prev[] -- the previous node of the ith node

   // c[][] -- every two nodes' distance

   void dijkstra(int n,int v,int *dist,int *prev,int c[maxnum][maxnum])

   {

      //初始化s集合//

  bool s[maxnum];

  與源點（目前點）相連接配接的點的點的距離記錄下來/

  for (int i=1;i<=n;i++)

  {

  dist[i]=c[v][i];

  s[i]=0;//初始都未使用過該點；

  if(dist[i]==maxint)

  {

  prev[i]=0;

  }

  else

  prev[i]=v;//該點前一個點為起始點//

  }

  dist[v]=0;

  s[v]=1;//第一個點在s集合中//

  //依次将未放入S集合的結點中取dist【】最小的結點放入s中

  //一旦S中包含了所有V中的頂點dist就記錄了從源點到所有其他頂點之間的最短路徑長度

  //注意是從第二個結點開始的第一個為源結點。//

  for(int i=2;i<=n;i++)

  {

  int tmp =maxint;

  int u =v;

  for (int j=1;j<=n;j++)

  {

  if (!s[j]&&dist[j]<tmp)//如果未通路過，且距離比最大值小

  {

  u=j;    //u儲存目前臨接點中距離最小的編号//

  tmp =dist[j];

  }

  }

  s[u]=1;//将u放入s中；

  //更新數組

  for(int i=1;i<=n;i++)

  {

               //中存放的是目前頂點；要用目前頂點算源點與各個點的距離//

 if (!s[i]&&c[u][i]<maxint)

 {

 int newdst =dist[u]+c[u][i];//上一個節點距離目前節點的值+目前節點離各個點，得到上一個點離該點的距離（途徑目前）；

 if (newdst<dist[i])//上一個節點直接到這個節點的距離大于，上一個節點途徑目前節點再到這個節點的距離；那麼就更新；

 {

 dist[i]=newdst;

 prev[i]=u;

 }

 }

  }

  }

   }

   void searchPath(int *prev,int v, int u)

   {

  int que[maxnum];

  int tot = 1;

  que[tot] = u;

  tot++;

  int tmp = prev[u];

  while(tmp != v)

  {

  que[tot] = tmp;

  tot++;

  tmp = prev[tmp];

  }

  que[tot] = v;

  for(int i=tot; i>=1; --i)

  if(i != 1)

  cout << que[i] << " -> ";

  else

  cout << que[i] << endl;

   }