Question

用dijkstra算法解决最短路径问题c语言代码实现时怎样将每一个路径的顶点次序依次输出出来？

Answer 1

void Dijkstra(int n,int v,int dist[],int prev[],int **cost)
{
  int i;
  int j;
    int maxint = 65535;//定义一个最大的数值，作为不相连的两个节点的代价权值
    int *s ;//定义具有最短路径的节点子集s
  s = (int *)malloc(sizeof(int) * n);
    //初始化最小路径代价和前一跳节点值
    for (i = 1; i <= n; i++)
    {
        dist[i] = cost[v][i];
        s[i] = 0;
        if (dist[i] == maxint)
        {
            prev[i] = 0;
        }
        else
        {
            prev[i] = v;
        }
    }
    dist[v] = 0;
    s[v] = 1;//源节点作为最初的s子集
    for (i = 1; i < n; i++)
    {
        int temp = maxint;
        int u = v;
        //加入具有最小代价的邻居节点到s子集
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (dist[j] < temp))
            {
                u = j;
                temp = dist[j];
            }
        }
        s[u] = 1;
        //计算加入新的节点后，更新路径使得其产生代价最短
        for (j = 1; j <= n; j++)
        {
            if ((!s[j]) && (cost[u][j] < maxint))
            {
                int newdist = dist[u] + cost[u][j];
                if (newdist < dist[j])
                {
                    dist[j] = newdist;
                    prev[j] = u;
                }
            }
        }
    }
}
//展示最佳路径函数
void ShowPath(int n,int v,int u,int *dist,int *prev)
{
 int j = 0;
 int w = u;
 int count = 0;
 int *way ;
 way=(int *)malloc(sizeof(int)*(n+1));
 //回溯路径
 while (w != v)
 {
  count++;
  way[count] = prev[w];
  w = prev[w];
 }
 //输出路径
 printf("the best path is:\n");
 for (j = count; j >= 1; j--)
 {
  printf("%d -> ",way[j]);
 }
 printf("%d\n",u);
}
//主函数，主要做输入输出工作
void main()
{
 int i,j,t;
  int n,v,u;
  
 int **cost;//代价矩阵
 int *dist;//最短路径代价
 int *prev;//前一跳节点空间
 printf("please input the node number: ");
  scanf("%d",&n);
  printf("please input the cost status:\n");
    
 cost=(int **)malloc(sizeof(int)*(n+1));
  for (i = 1; i <= n; i++)
  {
      cost[i]=(int *)malloc(sizeof(int)*(n+1));
  }
  //输入代价矩阵
  for (j = 1; j <= n; j++)
  {
      for (t = 1; t <= n; t++)
      {
          scanf("%d",&cost[j][t]);
      }
  }
    
  dist = (int *)malloc(sizeof(int)*n);
  prev = (int *)malloc(sizeof(int)*n);
  printf("please input the source node: ");
  scanf("%d",&v);
  //调用dijkstra算法  
  Dijkstra(n, v, dist, prev, cost);
  printf("*****************************\n");
 printf("have confirm the best path\n");
 printf("*****************************\n");
 for(i = 1; i <= n ; i++)
 {
  if(i!=v)
  {
   printf("the distance cost  from node %d to node %d is %d\n",v,i,dist[i]);
   printf("the pre-node of node %d is node %d \n",i,prev[i]);
   ShowPath(n,v,i, dist, prev);
  }
 }
}