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;

   }