最短路径迪杰克斯算法C++实现

#include
#include
#define MAX 10

/*邻接矩阵存储方式
cost[][]:二维数组，存放权值
n:顶点个数
distance[i]:i距离出发点的最短路径
path[i]:最短路径上i前面顶点的编号
s:出发点
*/
void shortestPath(int cost[][8], int n, int distance[], int path[], int s){
 //判断出发点有没有邻接点
 for(int i=0; i  if( cost[s][i] != MAX)
   break;
  else if(i == (n-1) ){
        printf("no adjvex\n");
        return;
  }
  
 //顶点v是否并入集合S中；
 bool isUnion[n];
 //初始化
 for(int i=0; i   distance[i] = MAX;
   path[i] = -1;
   isUnion[i] = false;
 }
 
 //初始化出发点相邻接的顶点距离
 for(int i =0; i      if(cost[s][i] != MAX){
       distance[i] = cost[s][i];
       path[i] = s;
      }
 }
 isUnion[s] = true;
 distance[s] = 0;
 
 //选择最短路径
 int min, t;
 for(int i=1; i      min = MAX;
      for(int j=0; j           if(!isUnion[j] && distance[j] < min){
            min = distance[j];
            t = j;
           }
          isUnion[t] = true;
         
          //更新t相邻点的值
          for(int k=0; k           if(cost[t][k] != MAX)
            if(!isUnion[k] && distance[k] > distance[t] + cost[t][k]){
             distance[k] = distance[t] + cost[t][k];
             path[k] = t;
            }
      }//for
 }//for
}//shortestPath()
 
/** 打印all路径 */
void printPath(int path[],int n, int distance[]){

     for(int i=0; i      int j = i;
      printf("到达顶点 %d 的最短长度和路径分别是：%d \n" , i, distance[i]);
      printf("%d", i);
      while(path[j] != -1){
       printf(" <-- ");
       printf("%d", path[j]);
       j = path[j];
      }
      printf("\n");
 }
}
/** 测试 */
int main()
{
 int s;
 int distance[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, distance, path, s);
 //call2
 printPath(path, 8,distance);
 //display
 system("pause");
}