// z2.cpp :Defines the entry point for the console application.
//
#include "stdafx.h"
//#include
//void main()
//{
#define MAXNUM 30
#define INFINITY 10000
#define FALSE 0
#define TRUE 1
#define BACK -1
#include "stdio.h"
#include
#include "malloc.h"
typedef struct{
char vexs[MAXNUM];
int edges[MAXNUM][MAXNUM];
int n,e;
}Mgraph;
void CreateGraph(Mgraph *g)
{
int i,j,k,w;
char ch;
printf("請輸入結點數與弧數,如：3,2：");
scanf("%d,%d",&(g->n),&(g->e));
for(i=0;in;i++)
{
for(j=0;jn;j++)
{
if(i==j){
g->edges[i][j]=0;
}else
{
g->edges[i][j]=INFINITY;
}
}
}
//擷取權值
printf("\n為友善示範,結點内容預設為結點序号,無需輸入.\n\n下面請輸入弧及權值,例如：若點0到1有弧可達,且權值為10,則輸入:0,1,10.注意：輸入時不區分弧的順序.\n");
for(k=0;ke;k++){
printf("\t請輸入第%d個弧及權值：",k+1);
scanf("%d,%d,%d",&i,&j,&w);
g->edges[i][j]=w;
}
//輸出鄰接矩陣
printf("\n鄰接矩陣：\n",k);
for(i=0;in;i++){
printf("\t");
for(j=0;jn;j++){
if(g->edges[i][j]>=INFINITY){
printf("∞\t");
}else{
printf("%d\t",g->edges[i][j]);
}
}
printf("\n");
}
}
void ShortPath(Mgraph *g,int v0)
{
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
//初始化遊标為零
for(i=0;in; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
//初始化v0的路徑距離為零,設定已擷取最短路徑
D[v0] = 0;
final[v0] = TRUE;
//主循環,擷取其他的最短路徑
for(i = 1;i < g->n; ++i){
min = INFINITY;
//尋找最小的D[w]
for(w = 0;w < g->n; ++w){
if(final[w] != TRUE){
if(D[w]n; ++w){
if((final[w] != TRUE) && (min+g->edges[v][w] < D[w])){
//更新路徑
iterator[w]=iterator[v];
for(j=0;jedges[v][w];
}
}
}
//若final始終為FALSE,則不可達
for(w = 0;wn; ++w){
if(final[w] != TRUE){
printf("\t點%d到點%d不可達\n",v0,w);
}
}
}
//主方法
void main()
{
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("該程式實作了Dijkstra算法,支援路徑顯示,請按提示輸入資料：\n\n");
CreateGraph(g);
printf("\n最小路徑判斷(以0點為起點)：\n");
ShortPath(g,0);
getchar();
}
解析看不懂？求助智能家教解答檢視解答