弗洛伊德算法有向图代码如下:
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include<limits.h>
#define MaxInt 32767
#define MVNum 100
int Path[MVNum][MVNum];//存放前驱索引的
int D[MVNum][MVNum];//存放当前已知的权值//图的邻接矩阵
typedef struct
{char vexs[MVNum];int arcs[MVNum][MVNum];int vexnum, arcnum;
}AMGraph;
int Locate(AMGraph G,char u)
{int i;for (i = 0; i < G.vexnum; i++){if (G.vexs[i] == u){return i;}}return -1;
}
void CreateAMGraph(AMGraph* G)
{int i, j, k, w;printf("请输入顶点数+边数\n");scanf("%d %d", &G->vexnum, &G->arcnum);getchar();printf("请输入顶点信息\n");for (i = 0; i < G->vexnum; i++){printf("请输入第%d个顶点:", i + 1);scanf(" %c", &G->vexs[i]);}printf("\n");for (i = 0; i < G->vexnum; i++){for (j = 0; j < G->vexnum; j++){if (j!=i){G->arcs[i][j] = MaxInt;}else {G->arcs[i][j] = 0;//初始二维数组全部赋极大值，然后j=i的就是自身的，那自身肯定没有权值的，直接给0}}}printf("请输入边依附的顶点和权值\n");for (k = 0; k < G->arcnum; k++){char v1, v2;printf("请输入第%d条边依附的顶点和权值:", k + 1);scanf(" %c %c %d", &v1, &v2, &w);i = Locate(*G, v1);j = Locate(*G, v2);G->arcs[i][j] = w;//更新arcs二维数组，把有权值的输入替换掉MaxInt}printf("邻接矩阵有向网创建成功\n");
}
void ShortestPath_Floyed(AMGraph G)
{int i, j, k;//把G.arcs的二维数组的权值信息先赋给D二维数组for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){//D(0)初始状态D[i][j] = G.arcs[i][j];//Path(0)初始状态if (D[i][j] < MaxInt && i!=j){Path[i][j] = i;}else {Path[i][j] = -1;}}}for (k = 0; k < G.vexnum; k++){for (i = 0; i < G.vexnum; i++){for (j = 0; j < G.vexnum; j++){if (D[i][k] + D[k][j] < D[i][j]){D[i][j] = D[i][k] + D[k][j];Path[i][j] = Path[k][j];}}}}
}
void DisplayPath(AMGraph G,int begin,int temp)
{if (Path[begin][temp] != -1){DisplayPath(G, begin, Path[begin][temp]);printf("%c --> ", G.vexs[Path[begin][temp]]);}
}
int main()
{printf("************算法6.11 弗洛伊德算法**************\n\n");AMGraph G;int num_start, num_destination;char start, destination;CreateAMGraph(&G);//这个函数的作用就是把D[MVNum][MVNum] 和 Path[MVNum][MVNum] 这两个数组弄成最终版本//迪杰斯特拉算法是把放入一个源点，然后列出所有 源点 - n个顶点的 边表达式//弗洛伊德算法 不需要放入源点，只是得到 D[MVNum][MVNum] 和 Path[MVNum][MVNum]的两份表格//通过看表格D可以知道(vi,vj)之间的最短距离的权值//通过看表格Path可以知道(vi,vk,vj)之间的边关系(前驱索引)ShortestPath_Floyed(G);printf("请输入起点和终点(vi,vj):");scanf(" %c %c", &start, &destination);num_start = Locate(G, start);num_destination = Locate(G, destination);DisplayPath(G, num_start, num_destination);printf("%c\n", G.vexs[num_destination]);printf("最短路径为:%d\n", D[num_start][num_destination]);
}弗洛伊德算法有向图图片如下：
弗洛伊德算法有向图终端输入如下:
************算法6.11 弗洛伊德算法**************
请输入顶点数+边数
4 8
请输入顶点信息
请输入第1个顶点:0
请输入第2个顶点:1
请输入第3个顶点:2
请输入第4个顶点:3请输入边依附的顶点和权值
请输入第1条边依附的顶点和权值:0 1 1
请输入第2条边依附的顶点和权值:0 3 4
请输入第3条边依附的顶点和权值:1 2 9
请输入第4条边依附的顶点和权值:1 3 2
请输入第5条边依附的顶点和权值:3 2 6
请输入第6条边依附的顶点和权值:2 3 8
请输入第7条边依附的顶点和权值:2 1 5
请输入第8条边依附的顶点和权值:2 0 3
邻接矩阵有向网创建成功
请输入起点和终点(vi,vj):1 2
1 --> 3 --> 2
最短路径为:8
源点为 1 ，终点为2 ，那么<1,3><3,2>为最短路径，权值为8,读者想使用其他的起点终点可以复制代码运行去验证
以下是有向图的D[w][w] 和Path[w][w]的信息:与上面的有向图对应的
