数据结构-迪杰斯特拉最短路径算法 （C语言代码）-------------C语言——菜鸟级

解题思路:

注意事项:

参考代码:

#include<stdio.h>
#include<string.h>
#define N 60
int dis[N];
int gxb[N][N];
int n,s;
void djsk()
{  int bj[N];
 memset(bj,0,sizeof(bj));
    int i,j,v=s,k=0,min=-1;
    for(i=0;i<n;i++)dis[i]=gxb[v][i];//初始化
    bj[v]=1;//标记 代表已经找到最短路
 for(i=1;i<n;i++)//最多需要寻找n-1次可以全部找到最短路
 {   k=0;min=-1;//最小值标记为-1 与 min=INF 等价
     for(j=0;j<n;j++)//从未找到最短路径元素中找一个路径最短的 
 if(!bj[j]&&dis[j]&&(dis[j]<min||min==-1))k=j,min=dis[j];
 //未找到最短路&&当前路径导通             找到最短的节点
  bj[k]=1;
 for(j=0;j<n;j++)//用但前最短路节点更新未找到最短路的节点
 if(!bj[j]&&gxb[k][j]&&(dis[j]>(dis[k]+gxb[k][j])||!dis[j]))dis[j]=dis[k]+gxb[k][j];
 //未找到最短路&&与当前节点导通&& 更新值大于之前的值
 }
}
int main()
{ memset(dis,0,sizeof(dis));
    int i,j,flag=0;
    scanf("%d%d",&n,&s);
    for(i=0;i<n;i++)
        for(j=0;j<n;j++)
         scanf("%d",&gxb[i][j]);
    djsk();
    i=0;
    for(i=0;i<n;i++)
    {if(i==s)continue;
     if(flag)printf(" ");
     if(dis[i]>0)printf("%d",dis[i]);
     else printf("-1");
      flag=1;
    }
    printf("\n");
    return 0;
}