最短路徑
對於使用者隨機輸入的一個有向帶權圖,求從某個頂點到其他各頂點的最短路徑
#include<stdio.h>
#define MAXV 20
#define INF 32 //若<vi,vj>不存在,則設<vi,vj>的權為32,表示無窮大
typedef struct
{ int no; /*頂點編號*/
// InfoType info; /*頂點其他資訊,此處省略*/
} VertexType; /*頂點型別*/
typedef struct
{ int edges[MAXV][MAXV]; /*鄰接矩陣*/
int n,e; /*頂點數,邊數*/
VertexType vexs[MAXV]; /*存放頂點資訊*/
}MatGraph; /*完整的圖鄰接矩陣型別*/
void Dispath(MatGraph g,int dist[],int path[],int s[],int v)
{ int i,j,k;
int apath[MAXV],d;
printf("\n");
for(i=0;i<g.n;i++)
if(s[i]==1 && i!=v)
{ printf("從頂點%d到頂點%d的路徑長度為:%d\t路徑為:",v,i,dist[i]);
d=0;apath[d]=i;
k=path[i];
if(k==-1)
printf("無路徑\n");
else
{ while(k!=v)
{ d++;apath[d]=k;
k=path[k];
}
d++;apath[d]=v;
printf("%d",apath[d]);
for(j=d-1;j>=0;j--)
printf(",%d",apath[j]);
printf("\n");
}
}
}
void Dijkstra(MatGraph g,int v)
{ int dist[MAXV],path[MAXV];
int s[MAXV];
int mindis,i,j,u;
for (i=0;i<g.n;i++)
{ dist[i]=g.edges[v][i]; //距離初始化
s[i]=0; //s[]置空
if(g.edges[v][i]<INF) //路徑初始化
path[i]=v; //頂點v到i有邊時,置頂點i的前一個頂點為v
else
path[i]=-1; //頂點v到i沒邊時,置頂點i的前一個頂點為-1
}
s[v]=1;path[v]=0; //源點編號v放入s中
for(i=0;i<g.n-1;i++) //迴圈直到所有頂點的最短路徑都求出
{ mindis=INF; //mindis置最小長度初值
for(j=0;j<g.n;j++) //選取不在s中且具有最小距離的頂點u
if(s[j]==0 && dist[j]<mindis)
{ u=j;
mindis=dist[j];
}
s[u]=1; //頂點u加入s中
for(j=0;j<g.n;j++) //修改不在s中的頂點的距離
if(s[j]==0)
if(g.edges[u][j]<INF && dist[u]+g.edges[u][j]<dist[j])
{ dist[j]=dist[u]+g.edges[u][j];
path[j]=u;
}
}
Dispath(g,dist,path,s,v); //輸出最短路徑
}
void main()
{ MatGraph G;
int V,i,j;
printf("請輸入圖G的頂點數和邊數(用逗號分隔):");
scanf("%d,%d",&G.n,&G.e);
getchar();
printf("請輸入圖G的頂點編號(用空格分隔):");
for(i=0;i<G.n;i++)
scanf("%d",&G.vexs[i].no);
getchar();
printf("請分行輸入圖G的鄰接矩陣(同一行的元素用空格分隔,每輸入完一行按回車結束):\n");
for(i=0;i<G.n;i++)
{ for(j=0;j<G.n;j++)
scanf("%d",&G.edges[i][j]);
getchar();
}
printf("請輸入源點V的編號:");
scanf("%d",&V);
Dijkstra(G,V);
}
執行結果
請輸入圖G的頂點數和邊數(用逗號分隔):5,8
請輸入圖G的頂點編號(用空格分隔):0 1 2 3 4
請分行輸入圖G的鄰接矩陣(同一行的元素用空格分隔,每輸入完一行按回車結束):
0 1 0 1 1
1 0 1 1 0
0 1 0 1 1
1 1 1 0 1
1 0 1 1 0
請輸入源點V的編號:0
從頂點0到頂點1的路徑長度為:1 路徑為:0,1
從頂點0到頂點2的路徑長度為:0 路徑為:0,2
從頂點0到頂點3的路徑長度為:1 路徑為:0,3
從頂點0到頂點4的路徑長度為:1 路徑為:0,4