// 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();
}
解析看不懂？求助智能家教解答查看解答