经典最短路径算法c c++ 邻接矩阵实现.txt

经典最短路径算法C C++ 邻接矩阵实现

 经典最短路径算法C/C++ 邻接矩阵实现

该算法的理论基础就不说了，保证贪婪法正确的理论证明可以采取假设的方式，很容易得到该算法的正确性。

#include<stdlib.h>
#include<stdio.h>
#define MAX 10
//p[][]:二维数组，存放权值 
//n:顶点个数
//d[i]:i距离出发点的最短路径
//path[i]:最短路径上i前面顶点的编号
//s:出发点 
void shortestPath(int p[][8], int n, int d[], int path[], int s)
{
 //判断出发点有没有邻接点
 for(int i=0; i<n; ++i)
  if( p[s][i] != MAX)
   break;
  else if(i == n)
   return; 
 //顶点v是否并入集合S中； 
 bool isUnion[n];
 //初始化
 for(int i=0; i<n; ++i)
 {
   d[i] = MAX;
   path[i] = -1;
   isUnion[i] = false;
 } 
 //初始化出发点相邻接的顶点距离
 for(int i =0; i<n; ++i)
 {
  if(p[s][i] != MAX)
  {
   d[i] = p[s][i];
   path[i] = s;
  }
 }
 isUnion[s] = true;
 d[s] = 0;
 //选择最短路径
 int min, t;
 for(int i=1; i<n; ++i)
 { 
  min = MAX;
  for(int j=0; j<n; ++j) //s编号不一定就是0，鄙视思维定势 
   if(!isUnion[j] && d[j] < min)
   {
    min = d[j];
    t = j;
   }
  isUnion[t] = true;
  //更新t相邻点的值 
  for(int k=0; k<n; ++k)
  {
   if(p[t][k] != MAX)
    if(!isUnion[k] && d[k] > d[t] + p[t][k])
    {
     d[k] = d[t] + p[t][k];
     path[k] = t;
    }
  }//for
 }//for
}//shortestPath()
 
/** 打印all路径 */
void printPath(int path[],int n, int d[])
{
 for(int i=0; i<n; ++i)
 {
  int j = i;
  printf("到达顶点 %d 的最短长度和路径分别是：%d \n" , i, d[i]); 
  printf("%d", i);
  while(path[j] != -1)
  { 
   printf(" <-- ");
   printf("%d", path[j]);
   j = path[j];
  } 
  printf("\n");
 } 
} 
/** 测试 */ 
int main()
{
 int s;
 int d[8], path[8];
 int w[8][8]={ 
      {10, 1, 10,10, 10, 4, 4, 10},
      {10, 10, 9, 10, 10, 2, 10, 10},
      {10, 10, 10, 1, 10, 10, 10, 10},
      {10, 10, 10, 10, 10, 10, 10, 10},
      {10, 10, 2, 5, 10, 10, 10, 10},
      {10, 10, 6, 10, 3, 10, 3, 4},
      {10, 10, 10, 10, 10, 10, 10, 7},
      {10, 10, 10, 3, 1, 10, 10, 10} 
    };
 printf("输入起点： \n");
 scanf("%d",&s);
    //call1
 shortestPath(w, 8, d, path, s);
 //call2
 printPath(path, 8,d);
 //display
 system("pause");
}