dijstra算法运行一直出错
头文件dijstra.h
#ifndef DIJSTRA_H_INCLUDED
#define DIJSTRA_H_INCLUDED
#define MAXVEX 100 /**< 最多顶点数 */
#define INFINITY 65535/**< 不存在该边是的权值 */
struct graph;
typedef struct graph *Graph;
typedef int VertexType;
typedef int EdgeType;
typedef int PathMatrix[MAXVEX];
typedef int ShortPathTable[MAXVEX];
struct graph
{
VertexType vertex[MAXVEX];
EdgeType edge[MAXVEX][MAXVEX];
int numvertex,numedge;
};
void CreatGraph(Graph G);/**< 创建图 */
void PrintGraph(Graph G);/**< 将图一临街矩阵的形式打印出来*/
void Dijstra(Graph G, int v0, PathMatrix *P, ShortPathTable *D);
#endif // DIJSTRA_H_INCLUDED
#include <stdio.h>
#include <malloc.h>
#include "dijstra.h"
void CreatGraph(Graph G)
{
int i,j,k,w;
printf("input the number of vertex ang edge:\n");
printf("the number of vertex :");
scanf("%d",&G->numvertex);
printf("\n");
printf("the number of edge:");
scanf("%d",&G->numedge);
/**< 输入顶点 */
for(i=0;i<G->numvertex;i++)
{
printf("输入第%d 顶点：",i+1);
scanf("%d",&G->vertex[i]);
}
/**< 矩阵初始化 */
for(i=0;i<G->numvertex;i++)
{
for(j=0;j<G->numedge;j++)
{
G->edge[i][j] = INFINITY;
}
}
/**< 输入边的权值此处一边控制循环次数 */
for(k=0;k<G->numedge;k++)
{
printf("input vertex and weight:\n");
scanf("%d %d %d",&i,&j,&w);
G->edge[i][j] = w;
G->edge[j][i] =G->edge[i][j];
}
}
void PrintGraph(Graph G)
{
int i,j;
for(i=0;i<G->numvertex;i++)
{
for(j=0;j<G->numvertex;j++)
{
if(G->edge[i][j] == INFINITY)
printf("\t**");
else
printf("\t%d",G->edge[i][j]);
}
printf("\n");
}
}
void Dijstra(Graph G, int v0, PathMatrix *P, ShortPathTable *D)
{
int v, w, k, min;
int final[MAXVEX];
for(v=0; v < G->numvertex; v++)
{
final[v] =0;
(*D)[v] = G->edge[v0][v];
(*P)[v] = 0;
}
(*D)[v0] = 0;
final[v0] = 1;
for(v=1; v < G->numvertex;v++)
{
min = INFINITY;
for(w=0; w < G->numvertex; w++)
{
if(!final[w] && (*D)[w] < min)
{
k=w;
min=(*D)[w];
}
}
final[k] = 1;
for(w=0; w < G->numvertex; w++)
{
if(!final[w] && min + G->edge[k][w] < (*D)[w])
{
(*D)[w] =min +G->edge[k][w];
(*P)[w] =k;
}
}
}
}
#include <stdio.h>
#include <stdlib.h>
#include "dijstra.c"
int main()
{
int v0;
PathMatrix *P;
ShortPathTable *D;
Graph G;
G=(Graph)malloc(sizeof(struct graph));
CreatGraph(G);
PrintGraph(G);
Dijstra(G, v0, P,D);
return 0;
}
/* c7-1.h 图的数组(邻接矩阵)存储表示 */
#define INFINITY INT_MAX /* 用整型最大值代替∞ */
#define MAX_VERTEX_NUM 20 /* 最大顶点个数 */
typedef enum{DG,DN,AG,AN}GraphKind; /* {有向图,有向网,无向图,无向网} */
typedef struct
{
VRType adj; /* 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否； */
/* 对带权图，c则为权值类型 */
InfoType *info; /* 该弧相关信息的指针(可无) */
}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef struct
{
VertexType vexs[MAX_VERTEX_NUM]; /* 顶点向量 */
AdjMatrix arcs; /* 邻接矩阵 */
int vexnum,arcnum; /* 图的当前顶点数和弧数 */
GraphKind kind; /* 图的种类标志 */
}MGraph;
/* algo7-6.c 实现算法7.15的程序。迪杰斯特拉算法的实现 */
#include"c1.h"
#define MAX_NAME 5 /* 顶点字符串的最大长度+1 */
#define MAX_INFO 20 /* 相关信息字符串的最大长度+1 */
typedef int VRType;
typedef char InfoType;
typedef char VertexType[MAX_NAME];
#include"c7-1.h"
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
#include"bo7-1.c"
void ShortestPath_DIJ(MGraph G,int v0,PathMatrix *P,ShortPathTable *D)
{ /* 用Dijkstra算法求有向网G的v0顶点到其余顶点v的最短路径P[v]及带权长度 */
/* D[v]。若P[v][w]为TRUE,则w是从v0到v当前求得最短路径上的顶点。 */
/* final[v]为TRUE当且仅当v∈S,即已经求得从v0到v的最短路径 算法7.15 */
int v,w,i,j,min;
Status final[MAX_VERTEX_NUM];
for(v=0;v<G.vexnum;++v)
{
final[v]=FALSE;
(*D)[v]=G.arcs[v0][v].adj;
for(w=0;w<G.vexnum;++w)
(*P)[v][w]=FALSE; /* 设空路径 */
if((*D)[v]<INFINITY)
{
(*P)[v][v0]=TRUE;
(*P)[v][v]=TRUE;
}
}
(*D)[v0]=0;
final[v0]=TRUE; /* 初始化,v0顶点属于S集 */
for(i=1;i<G.vexnum;++i) /* 其余G.vexnum-1个顶点 */
{ /* 开始主循环,每次求得v0到某个v顶点的最短路径,并加v到S集 */
min=INFINITY; /* 当前所知离v0顶点的最近距离 */
for(w=0;w<G.vexnum;++w)
if(!final[w]) /* w顶点在V-S中 */
if((*D)[w]<min)
{
v=w;
min=(*D)[w];
} /* w顶点离v0顶点更近 */
final[v]=TRUE; /* 离v0顶点最近的v加入S集 */
for(w=0;w<G.vexnum;++w) /* 更新当前最短路径及距离 */
{
if(!final[w]&&min<INFINITY&&G.arcs[v][w].adj<INFINITY&&(min+G.arcs[v][w].adj<(*D)[w]))
{ /* 修改D[w]和P[w],w∈V-S */
(*D)[w]=min+G.arcs[v][w].adj;
for(j=0;j<G.vexnum;++j)
(*P)[w][j]=(*P)[v][j];
(*P)[w][w]=TRUE;
}
}
}
}
void main()
{
int i,j,v0=0; /* v0为源点 */
MGraph g;
PathMatrix p;
ShortPathTable d;
CreateDN(&g);
ShortestPath_DIJ(g,v0,&p,&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=1;i<g.vexnum;++i)
printf("%s-%s:%d\n",g.vexs[0],g.vexs[i],d[i]);
}
