输出的显然路径是错的，不知道算法哪里写错了？
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#define MaxVertexNum 100
#define Infinity 3000
typedef int Vertex;
typedef char DataType;
struct ENode {
Vertex V1,V2;
int Weight;
};
typedef struct ENode *Edge;
struct GNode{
Vertex Gmat[MaxVertexNum][MaxVertexNum];
DataType Data[MaxVertexNum][10]; //可选：顶点存储的数据
int Nv; //顶点数
int Ne; //边数
};
typedef struct GNode *Gragh;
Gragh Initialize(int VertexNum);
void InsertEdge(Gragh G,Edge E);
Gragh BuildGragh();
void Dijkstra(Gragh G,Vertex S);
Vertex FindMin(Gragh G);
void PrintMinPath(Gragh G);
void Floyd(Gragh G);
void PrintPath(Vertex f,Vertex t);
#include "Gragh-mat.h"
Gragh Initialize(int VertexNum){
Gragh G = (Gragh)malloc(sizeof(struct GNode));
G->Nv = VertexNum;
G->Ne = 0;
for (int i = 0;i < VertexNum;i++)
{
for (int j = 0;j < VertexNum;j++)
G->Gmat[i][j] = Infinity; //自己到自己也是infinity
}
return G;
}
void InsertEdge(Gragh G,Edge E){
G->Gmat[E->V1][E->V2] = E->Weight;
G->Gmat[E->V2][E->V1] = E->Weight; //可选：无向图加上这一句
}
Gragh BuildGragh(){
int Nv,Ne;
int v1,v2,weight;
Edge E;
do
{
printf("Please enter a number less than 100:");
scanf("%d",&Nv);
} while (Nv >= 100);
Gragh G = Initialize(Nv);
printf("Input the number of edges:");
scanf("%d",&Ne);
G->Ne = Ne;
if (G->Ne != 0)
{
E = (Edge)malloc(sizeof(struct ENode));
printf("please add edges for your gragh.format:Vec1 Vec2 Weight.\n");
for (int i = 0;i < G->Ne;i++)
{
scanf("%d %d %d",&v1,&v2,&weight);
E->V1 = v1;
E->V2 = v2;
E->Weight = weight;
InsertEdge(G,E);
}
}
/*以下是可选的数据录入*/
//printf("Please add data for each vertex.");
//for (int i = 0;i < G->Nv;i++)
//{
// scanf("%s",G->Data[i]);
//}
return G;
}
int Dist[][MaxVertexNum];
Vertex Path[][MaxVertexNum];
void Floyd(Gragh G){
for (int i = 0;i < G->Nv;i++)
{
for (int j = 0;j < G->Nv;j++)
{
Dist[i][j] = G->Gmat[i][j];
Path[i][j] = -1;
}
}
for (int k = 0;k < G->Nv;k++)
{
for (int i = 0;i < G->Nv;i++)
{
for (int j = 0;j < G->Nv;j++)
{
if (Dist[i][k] + Dist[k][j] < Dist[i][j])
{
Dist[i][j] = Dist[i][k] + Dist[k][j];
Path[i][j] = k;
}
}
}
}
}
void PrintPath(Vertex f,Vertex t){
Vertex pass;
if (Path[f][t] = -1)
printf("<%d,%d>",f,t);
else
{
pass = Path[f][t];
PrintPath(f,pass);
PrintPath(pass,t);
}
}
int main()
{
Gragh G = BuildGragh();
Floyd(G);
PrintPath(0,5);
return 0;
}
