xixi.cpp

Dijlstra算法 对任意图

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX_NAME 10
#define MAX_V_N 26
#define MAX 32768
typedef char VertexData[MAX_NAME];
typedef int AdjMatrix[MAX_V_N][MAX_V_N];//邻接距阵
struct MGraph//定义网
{
VertexData vexs[MAX_V_N];
AdjMatrix arcs;
int vexnum,arcnum;
};
int LocateVex(MGraph G,VertexData u)//定位
{
int i;
for(i=0;i<G.vexnum;++i)if(strcmp(u,G.vexs[i])==0)return i;
return -1;
}
void CreateDN(MGraph &G)//建网
{
int i,j,k,weight;
VertexData v1,v2;
printf("请输入有向网G的顶点数和弧数(以空格作为间隔)\n");
scanf("%d %d",&G.vexnum,&G.arcnum);
printf("请输入%d个顶点的值(<%d个字符):\n",G.vexnum,MAX_NAME);
for(i=0;i<G.vexnum;++i)
scanf("%s",G.vexs[i]);
for(i=0;i<G.vexnum;++i)
for(j=0;j<G.vexnum;++j)
G.arcs[i][j]=MAX;
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n",G.arcnum);
for(k=0;k<G.arcnum;++k)
{
scanf("%s%s%d%*c",v1,v2,&weight);
i=LocateVex(G,v1);
j=LocateVex(G,v2);
G.arcs[i][j]=weight;
}
}

typedef int PathMatrix[MAX_V_N][MAX_V_N];
typedef int ShortPathTable[MAX_V_N];

void ShortestPath_DIJ(MGraph G,int v0,PathMatrix P,ShortPathTable Dist)
{
int v,w,i,min;
int s[MAX_V_N];
for(v=0;v<G.vexnum;++v)
{
s[v]=0;
Dist[v]=G.arcs[v0][v];
for(w=0;w<G.vexnum;++w)
P[v][w]=0;
if(Dist[v]<MAX)
P[v0][v]=1;
}
Dist[v0]=0;
s[v0]=1;
for(i=1;i<G.vexnum;++i)
{
min=MAX;
for(w=0;w<G.vexnum;++w)
if(s[w]!=1&&Dist[w]<min)
{
v=w;
min=Dist[w];
}
s[v]=1;
for(w=0;w<G.vexnum;++w)
if(s[w]!=1&&min<MAX&&G.arcs[v][w]<MAX&&G.arcs[w][v]<MAX&&(min+G.arcs[v][w]<Dist[w]))
{
Dist[w]=min+G.arcs[v][w];
P[v][w]=1;
P[w][v]=1;
}
}
}

int main()
{
int i,j;
MGraph g;
PathMatrix p;
ShortPathTable d;
CreateDN(g);
ShortestPath_DIJ(g,0,p,d);//以g中位置为0的顶点为源点，球其到其余各顶点的最短距离。存于d中
printf("最短路径数组p[i][j]如下:\n");
for(i=0;i<g.vexnum;++i)
{
for(j=0;j<g.vexnum;++j)
printf("%2d",p[i][j]);
printf("\n");
}
printf("%s到各顶点的最短路径长度为：\n",g.vexs[0]);
for(i=0;i<g.vexnum;++i)
if(i!=0)
{
if(d[i]-MAX)printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);
else printf("%s-%s:无路\n",g.vexs[0],g.vexs[i]);
}
system("PAUSE");
return 0;
}