// 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("請(qǐng)輸入結(jié)點(diǎn)數(shù)與弧數(shù),如：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;
}
}
}
//獲取權(quán)值
printf("\n為方便演示,結(jié)點(diǎn)內(nèi)容默認(rèn)為結(jié)點(diǎn)序號(hào),無(wú)需輸入.\n\n下面請(qǐng)輸入弧及權(quán)值,例如：若點(diǎn)0到1有弧可達(dá),且權(quán)值為10,則輸入:0,1,10.注意：輸入時(shí)不區(qū)分弧的順序.\n");
for(k=0;ke;k++){
printf("\t請(qǐng)輸入第%d個(gè)弧及權(quán)值：",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)
{
/*定義多個(gè)變量與數(shù)組,其中R數(shù)組為記錄路徑的數(shù)組,iterator為游標(biāo),
D為距離數(shù)組,final數(shù)組記錄是否已取到最短路徑
*/
int i,j,v,w,min;
int R[MAXNUM][MAXNUM];
int iterator[MAXNUM];
int D[MAXNUM];
int final[MAXNUM];
//初始化游標(biāo)為零
for(i=0;in; ++v){
final[v] = FALSE;
D[v] = g->edges[v0][v];
}
//初始化v0的路徑距離為零,設(shè)置已獲取最短路徑
D[v0] = 0;
final[v0] = TRUE;
//主循環(huán),獲取其他的最短路徑
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,則不可達(dá)
for(w = 0;wn; ++w){
if(final[w] != TRUE){
printf("\t點(diǎn)%d到點(diǎn)%d不可達(dá)\n",v0,w);
}
}
}
//主方法
void main()
{
Mgraph * g;
int i=0;
g=(Mgraph *)malloc(sizeof(Mgraph));
printf("該程序?qū)崿F(xiàn)了Dijkstra算法,支持路徑顯示,請(qǐng)按提示輸入數(shù)據(jù)：\n\n");
CreateGraph(g);
printf("\n最小路徑判斷(以0點(diǎn)為起點(diǎn))：\n");
ShortPath(g,0);
getchar();
}