迪杰斯特拉算法
-----------data.txt-----------
6 8
0 0 100 30 0 10
0 0 0 0 0 5
0 0 0 0 0 0
0 0 60 0 20 0
0 0 10 0 0 0
0 0 0 0 50 0
----------code.cpp----------
\#include\
\#include\
\#include\
\#define Max\_vnum 50
int final[Max\_vnum];
int D[Max\_vnum];
typedef struct Path{int adj;struct Path \*next;}Path;
Path \*P[Max\_vnum];
typedef struct {
int arc[Max\_vnum][Max\_vnum];
int vexnum,arcnum;
}MGraph;
void InitGraph(MGraph &G)
{
FILE \*fin;
int t;
fin=fopen("data.txt","r");
fscanf(fin,"%d%d",&G.vexnum,&G.arcnum);
for(int i=0;i\
{
for(int j=0;j\
{
fscanf(fin,"%d",&t);
if(t==0)
G.arc[i][j]=INT\_MAX;
else
G.arc[i][j]=t;
}
}
return ;
}
void ShortestPath\_DIJ(MGraph G,int v0)
{
int min,w,v,isend=-1;
Path \*p;
for(v=0;v\
{
final[v]=0;
D[v]=G.arc[v0][v];
P[v]=(Path\*)malloc(sizeof(Path));
P[v]-\>next=NULL;
p=(Path\*)malloc(sizeof(Path));
p-\>adj=v0;
p-\>next=NULL;
P[v]-\>next=p;
}
D[v0]=0;
final[v0]=1;
for(int i=1;i\
{
min=INT\_MAX;
for(w=0;w\
if(!final[w])
if(D[w]\
{
min=D[w];
v=w;
}
if(isend==v)
break;
isend=v;
final[v]=1;
for(p=P[v]-\>next;p-\>next;p=p-\>next)
printf("v%d",p-\>adj)
printf("v%d",p-\>adj);
Path \*p2;
p2=(Path\*)malloc(sizeof(Path));
p2-\>adj=v;
p2-\>next=NULL;
p-\>next=p2;
printf("v%dn",v);
for(w=0;w\
if(!final[w]&&G.arc[v][w]!=INT\_MAX&&(min+G.arc[v][w]\
{
//printf("%d %d %d n",min,G.arc[v][w],D[w]);
D[w]=min+G.arc[v][w];
P[w]=P[v];
}
}
return ;
}
int main()
{
MGraph G;
InitGraph(G);
ShortestPath\_DIJ(G,0);
getchar();
return 0;
}
----------Output----------
v0v5
v0v3
v0v3v4
v0v3v4v2
算是打出正确结果了，改天再认真研究一下。
Comments