新手求助 迪杰斯特拉算法
#include<stdio.h>#include<stdlib.h>
#define INFINITY 1000000000
#define MAX 10 //图中最大顶点个数
typedef struct MGraph
{
char vexs[MAX];
int arcs[MAX][MAX];
int vexnum, arcnum;
}MGraph;
//定位顶点
int LocateVex(MGraph G,char v)
{
int i;
for(i=0;i<G.vexnum;i++)
if(v==G.vexs[i])
return i;
return -1;
}
//建立邻接矩阵存储的有向网
void CreatedMGraph(MGraph &G)
{
int i,j,v;
char v1,v2;
int weights;
printf("请输入顶点数和边数:");
scanf("%d%d",&G.vexnum,&G.arcnum);
for(i=0;i<G.vexnum;i++)
for(j=0;j<G.vexnum;j++)
G.arcs[i][j]=INFINITY;
printf("请输入顶点:");
for(v=0;v< G.vexnum;v++)
{
G.vexs[v]=getchar();
}
printf("请输入边及边的权值:");
for(v=0;v<G.arcnum;v++)
{
scanf("%c%c",&v1,&v2);
scanf("%d",&weights);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=weights;
}
}
//利用Dijkstra算法求有向网G的从顶点v0到其他各顶点的最短路径
void ShortestPath_DIJ(MGraph G, int v0, int P[MAX][MAX],int D[MAX])
{
int v,i;
int w,j;
int final[MAX];//到顶点v最短路径是否找到
//初始化
for (v=0; v<G.vexnum; ++v)
{
final[v]=0;
D[v]=G.arcs[v0][v];
for (i=0; i<G.vexnum; ++i)
{
P[v][i]=0; //初始路径为空
}
if (D[v]<INFINITY)
{
P[v][v0]=1;
P[v][v]=1;
}
} //for
D[v0]=0;
final[v0]=1;
//下面是每次求得v0到某个v顶点的最短路径，并加v到S集
for (i=1; i<G.vexnum; ++i)
{
int min=1000;
for (j=0; j<G.vexnum;++j) //求v0到w的最短路径
{
if(!final[j])
if(D[j]<min)
{
v=j;
min=D[j];
}
}
final[v]=1;
for (w=0; w<G.vexnum; ++w) //更新到T中顶点的最短路径
if (!final[w] && (min+G.arcs[v][w]<D[w] ))
{
D[w]=min+G.arcs[v][w];
for(j=0;j<G.vexnum;++j)
P[w][j]=P[v][j];
P[w][w]=1;
}
}
for (v=0; v<G.vexnum; ++v)
{
for(i=0;i<G.vexnum;i++)
{
if(P[v][i])
printf("%c",G.vexs[i]);
}
printf("\n");
}
}
void main()
{
MGraph G;
int v,i;
int P[MAX][MAX];//最短路径数组
int D[MAX]; //最短路径长度
CreatedMGraph(G);
printf("%d,%d",G.vexnum,G.arcnum);
for (v=0; v<G.vexnum; ++v)
{
printf("%c",G.vexs[v]);
for(i=0;i<G.vexnum;i++)
{
printf("%c",G.arcs[v][i]);
}
}
printf("请输入所求最短路径的顶点:");
scanf("%c",&v);
getchar();
i=LocateVex(G,v);
ShortestPath_DIJ(G,i,P,D);
}
不知道哪里错了
求帮助
