弗洛伊德算法有向图代码如下:
#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]的信息:与上面的有向图对应的
