写了一个下午的Dijkstra（迪杰斯特拉）算法 （其实写了1个小时 其余时间一直在改错还是最后结果不匹配? ? 找了一个下午终于找到了? ?是输入邻接矩阵时 在没有路线时原本是输入-1 结果不对? 经过调整? 输入32767? 结果正确）希望在我身上发生的能让个位看官避雷而且希望我的代码可以对更多人有帮助。
跟着小v不迷路，希望给小v一个三连。上代码。
# include <stdio.h>
# define max 100
typedef struct {
int v[max]; //定点表
int arc[max][max]; //邻接矩阵
int vnum , bnum; //定点数 边数
} tu;
tu creat (tu t)
{
printf("请输入定点数和边数");
//输入顶点数 边数
scanf("%d",&(t.vnum));
// printf("进行到这了");
scanf("%d",&(t.bnum));
for(int i=0;i<t.vnum;i++) //初始化 顶点表
{
printf("请输入顶点");
scanf("%d",&t.v[i]);
}
printf("请输入边的权值");
for(int i=0;i<t.vnum;i++)
{
for(int j=0;j<t.vnum;j++)
{
scanf("%d",&t.arc[i][j]);
}
}
for(int i=0;i<t.vnum;i++)
{
for(int j=0;j<t.vnum;j++)
{
printf("%d ",t.arc[i][j]);
}
printf("\n");
}
return t;
}
int findmin(int *dist,int *s,int n)
{
int j,k=0;
int min=32767;
for(j=0;j<n;j++)
{
if((s[j]==0)&&(dist[j]<min))
{
min=dist[j];
k=j;
}
}
// if(k==0)
// return -1;
// else
return k;
}
/*
存储结构 带权的邻接矩阵 因为要随时读取数据 所以用邻接矩阵
按路径长度递增的次序产生最短路径的算法
dist[]数组 存储权值 没有就赋值为-1 不考虑s数组中的顶点
path[]数组 表示找到了从初始点到vi的最短路径 存双亲节点
若有弧长 则为0 否则为-1
s[]数组 存放源点和已经生成的终点 初始状态只有起点
*/
void Djstl(tu t)
{
int i,min,num;
int dist[t.vnum];
int path[t.vnum];
int s[t.vnum];
//初始化
//先以第一行的权值进行赋值
for(i=0;i<t.vnum;i++)
{
s[i]=0; //初始化均为0 表示未进入路径 进入路径为1
dist[i]=t.arc[0][i]; //表示 0 到各个顶点的距离 未相连接为-1
if(dist[i]!=32767) //表示为 某个点到到改点有路径 可以到达
{
path[i]=0 ; // 初始化 所有点的父顶点都为0号源点
}
else
path[i]=-1;
}
s[0]=1 ; //表示已经进入路径
num=1;
while(num<t.vnum)
{
min=findmin(dist,s,t.vnum);
s[min]=1;
for(i=0;i<t.vnum;i++)
{
if((s[i]==0)&&(dist[i]>dist[min]+t.arc[min][i]) )
{
dist[i]=dist[min] + t.arc[min][i];
path[i]=min;
// printf("%d",num); if 只进行了3次
}
}
num++;
// printf("%d\n",num);
}
printf("输出的是dist数组:");
for(i=0;i<t.vnum;i++)
{
printf("%d ",dist[i]);
}
printf("\n");
printf("输出的是path数组:");
for(i=0;i<t.vnum;i++)
{
printf("%d ",path[i]);
}
printf("\n");
printf("输出的是数组:");
for(i=0;i<t.vnum;i++)
{
printf("%d ",s[i]);
}
}
int main()
{
tu t;
t=creat(t);
Djstl(t);
return 0;
}
