#include <stdio.h>
#include <stdlib.h>
#define MAXN 10
#define INF = 1000
typedef struct struct_graph{
char vexs[MAXN];
int vexnum;//顶点数
int edgnum;//边数
} Graph;
void CreateMGraph(Graph *G)
{
int i , j , k , w ;
printf("请输入顶点数与边数(输入格式为:顶点数,边数):") ;
scanf("%d,%d" , &G->vexnum , &G->edgnum) ;
printf("请输入顶点信息(输入格式为:顶点号):\n") ;
for(i = 0 ; i < G->vexnum ; i++)
{
scanf("%s" , G->vexs[i]) ;
}
}
void short_path_floyd(Graph G, int P[MAXN][MAXN], int D[MAXN][MAXN]){
int v, w, k;
//初始化floyd算法的两个矩阵
for(v = 0; v < G.vexnum; v++){
for(w = 0; w < G.vexnum; w++){
D[v][w] = G.edgnum[v][w];
P[v][w] = w;
}
}
//这里是弗洛伊德算法的核心部分
//k为中间点
for(k = 0; k < G.vexnum; k++){
//v为起点
for(v = 0 ; v < G.vexnum; v++){
//w为终点
for(w =0; w < G.vexnum; w++){
if(D[v][w] > (D[v][k] + D[k][w])){
D[v][w] = D[v][k] + D[k][w];//更新最小路径
P[v][w] = P[v][k];//更新最小路径中间顶点
}
}
}
}
printf("\n初始化的D矩阵\n");
for(v = 0; v < G.vexnum; v++){
for(w = 0; w < G.vexnum; w++){
printf("%d ", D[v][w]);
}
printf("\n");
}
printf("\n初始化的P矩阵\n");
for(v = 0; v < G.vexnum; v++){
for(w = 0; w < G.vexnum; w++){
printf("%d", P[v][w]);
}
printf("\n");
}
v = 0;
w = 3;
//求 0 到 3的最小路径
printf("\n%d -> %d 的最小路径为:%d\n", v, w, D[v][w]);
k = P[v][w];
printf("path: %d", v);//打印起点
while(k != w){
printf("-> %d", k);//打印中间点
k = P[k][w];
}
printf("-> %d\n", w);
}
int main() {
printf("输入有向图的顶点数n:");
int n;
scanf("%d",&n);
printf("输入有向图的带权邻接矩阵(-1表示不可达):\n");
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
scanf("%d",&input[i][j]);
}
}
Floyd(n);
printf("任意两点最短路径的邻接矩阵:\n");
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
printf("%d ",G.matirx[i][j]);
}
printf("\n")