知识点
Floyd 算法
是用来求任意两个结点之间的最短路的;
复杂度比较高，但是常数小，容易实现。（我会说只有三个 for 吗？）
适用于任何图，不管有向无向，边权正负，但是最短路必须存在。（不能有个负环）
算法实现
我们定义一个数组 f[k][x][y]，表示只允许经过结点 1 1 1 到 k k k（也就是说，在子图 V ′ = 1 , 2 , 3 , . . . , k V' = 1,2,3,...,k V′=1,2,3,...,k 中的路径，注意， x x x 与 y y y 不一定在这个子图中），结点 x x x 到结点 y y y 的最短路长度。
很显然，f[n][x][y] 就是结点 x x x 到结点 y y y 的最短路长度（因为 V ′ = 1 , 2 , 3 , . . . , n V' = 1,2,3,...,n V′=1,2,3,...,n 即为 V V V 本身，其表示的最短路径就是所求路径）。
接下来考虑如何求出k数组的值。
f[0][x][y]： x x x 与 y y y 的边权，或者 0 0 0，或者 + ∞ +∞ +∞（f[0][x][y] 什么时候应该是 + ∞ +∞ +∞？当 x x x 与 y y y 间有直接相连的边的时候，为它们的边权；当 x = y x=y x=y 的时候为零，因为到本身的距离为零；当 x x x 与 y y y 没有直接相连的边的时候，为 + ∞ +∞ +∞）。
f[k][x][y] = min(f[k-1][x][y], f[k-1][x][k]+f[k-1][k][y])（f[k-1][x][y]，为不经过 k k k 点的最短路径，而 f[k-1][x][k]+f[k-1][k][y]，为经过了 k k k 点的最短路）。
上面两行都显然是对的，所以说这个做法空间是 O ( N 3 ) O(N^3) O(N3)，我们需要依次增加问题规模（ k k k 从 1 1 1 到 n n n），判断任意两点在当前问题规模下的最短路。
//算法7.16
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
void ShortestPath_FLOYD(MGraph G, int (*P)[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM], DistancMatrix *D){
int u, v, w, i;
for (v = 0; v < G.vexnum; v++) // 各对结点之间初始已知路径及距离
for (w = 0; w < G.vexnum; w++){
(*D)[v][w] = G.arcs[v][w].adj;
for (u = 0; u < G.vexnum; u++)
(*P)[v][w][u] = FALSE;
if ((*D)[v][w] < INFINITY) {
(*P)[v][w][v] = TRUE;
(*P)[v][w][w] = TRUE;
}
}
for (u = 0; u < G.vexnum; u++)
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
if ((*D)[v][u] + (*D)[u][w] < (*D)[v][w]) {
(*D)[v][w] = (*D)[v][u] + (*D)[u][w];
for (i = 0; i < G.vexnum; i++)
(*P)[v][w][i] = (*P)[v][u][i] || (*P)[u][w][i];
}
}
完整代码
#include<bits/stdc++.h>
using namespace std;
/* 函数结果状态代码 */
#define TRUE 1
#define FALSE 0
#define OK 1
#define ERROR 0
#define INFEASIBLE -1
#define OVERFLOW -2
#define MAX_NAME 5 // 顶点字符串的最大长度+1
#define MAX_INFO 20 // 相关信息字符串的最大长度+1
typedef int VRType;
typedef char VertexType[MAX_NAME];
typedef char InfoType;
typedef int Status;
typedef int Boolean;
/* --------------------------------- 图的数组(邻接矩阵)存储表示 --------------------------------*/
#define INFINITY INT_MAX // 用整型最大值代替∞
#define MAX_VERTEX_NUM 20 // 最大顶点个数
typedef enum {
DG, DN, AG, AN }GraphKind; // {有向图,有向网,无向图,无向网}
typedef struct{
VRType adj;
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;
typedef int PathMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
typedef int ShortPathTable[MAX_VERTEX_NUM];
/* --------------------------- 需要用的图的数组(邻接矩阵)存储的基本操作 --------------------------*/
int LocateVex(MGraph G, VertexType u){
int i;
for (i = 0; i < G.vexnum; ++i)
if (strcmp(u, G.vexs[i]) == 0)
return i;
return -1;
}
Status CreateDN(MGraph *G){
// 采用数组(邻接矩阵)表示法,构造有向网G
int i, j, k, w, IncInfo;
char s[MAX_INFO], *info;
VertexType va, vb;
printf("请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(空格隔开): ");
scanf("%d%d%d", &(*G).vexnum, &(*G).arcnum, &IncInfo);
printf("请输入%d个顶点的值(<%d个字符):\n", (*G).vexnum, MAX_NAME);
for (i = 0; i < (*G).vexnum; ++i) // 构造顶点向量
scanf("%s", (*G).vexs[i]);
for (i = 0; i < (*G).vexnum; ++i) // 初始化邻接矩阵
for (j = 0; j < (*G).vexnum; ++j){
(*G).arcs[i][j].adj = INFINITY; // 网
(*G).arcs[i][j].info = NULL;
}
printf("请输入%d条弧的弧尾 弧头 权值(以空格作为间隔): \n", (*G).arcnum);
for (k = 0; k < (*G).arcnum; ++k){
scanf("%s%s%d%*c", va, vb, &w); // %*c吃掉回车符
i = LocateVex(*G, va);
j = LocateVex(*G, vb);
(*G).arcs[i][j].adj = w;
if (IncInfo){
printf("请输入该弧的相关信息(<%d个字符): ", MAX_INFO);
gets(s);
w = strlen(s);
if (w){
info = (char*)malloc((w + 1) * sizeof(char));
strcpy(info, s);
(*G).arcs[i][j].info = info;
}
}
}
(*G).kind = DN;
return OK;
}
//算法7.16
typedef int DistancMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];
void ShortestPath_FLOYD(MGraph G, int (*P)[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM], DistancMatrix *D){
int u, v, w, i;
for (v = 0; v < G.vexnum; v++) // 各对结点之间初始已知路径及距离
for (w = 0; w < G.vexnum; w++){
(*D)[v][w] = G.arcs[v][w].adj;
for (u = 0; u < G.vexnum; u++)
(*P)[v][w][u] = FALSE;
if ((*D)[v][w] < INFINITY) {
(*P)[v][w][v] = TRUE;
(*P)[v][w][w] = TRUE;
}
}
for (u = 0; u < G.vexnum; u++)
for (v = 0; v < G.vexnum; v++)
for (w = 0; w < G.vexnum; w++)
if ((*D)[v][u] + (*D)[u][w] < (*D)[v][w]) {
(*D)[v][w] = (*D)[v][u] + (*D)[u][w];
for (i = 0; i < G.vexnum; i++)
(*P)[v][w][i] = (*P)[v][u][i] || (*P)[u][w][i];
}
}
int main(){
MGraph g;
int i, j, k, l, m, n;
int p[MAX_VERTEX_NUM][MAX_VERTEX_NUM][MAX_VERTEX_NUM];
DistancMatrix d;
CreateDN(&g);
for (i = 0; i < g.vexnum; i++)
g.arcs[i][i].adj = 0; // ShortestPath_FLOYD()要求对角元素值为0
printf("邻接矩阵:\n");
for (i = 0; i < g.vexnum; i++){
for (j = 0; j < g.vexnum; j++)
printf("%11d", g.arcs[i][j]);
printf("\n");
}
ShortestPath_FLOYD(g, &p, &d);
printf("d矩阵:\n");
for (i = 0; i < g.vexnum; i++){
for (j = 0; j < g.vexnum; j++)
printf("%6d", d[i][j]);
printf("\n");
}
for (i = 0; i < g.vexnum; i++)
for (j = 0; j < g.vexnum; j++)
printf("%s到%s的最短距离为%d\n", g.vexs[i], g.vexs[j], d[i][j]);
printf("p矩阵:\n");
l = strlen(g.vexs[0]); // 顶点向量字符串的长度
for (i = 0; i < g.vexnum; i++){
for (j = 0; j < g.vexnum; j++){
if (i != j){
m = 0; // 占位空格
for (k = 0; k < g.vexnum; k++)
if (p[i][j][k] == 1)
printf("%s", g.vexs[k]);
else
m++;
for (n = 0; n < m*l; n++) // 输出占位空格
printf(" ");
}
else
for (k = 0; k < g.vexnum*l; k++) // 输出占位空格
printf(" ");
printf(" "); // 输出矩阵元素之间的间距
}
printf("\n");
}
}
测试样例
请输入有向网G的顶点数,弧数,弧是否含其它信息(是:1,否:0)(空格隔开): 3 5 0
请输入3个顶点的值(<5个字符):
v0 v1 v2
请输入5条弧的弧尾 弧头 权值(以空格作为间隔):
v0 v1 4
v0 v2 11
v2 v0 3
v1 v0 6
v1 v2 2
运行结果
邻接矩阵:
0 4 11
6 0 2
3 2147483647 0
d矩阵:
0 4 6
5 0 2
3 7 0
v0到v0的最短距离为0
v0到v1的最短距离为4
v0到v2的最短距离为6
v1到v0的最短距离为5
v1到v1的最短距离为0
v1到v2的最短距离为2
v2到v0的最短距离为3
v2到v1的最短距离为7
v2到v2的最短距离为0
p矩阵:
v0v1 v0v1v2
v0v1v2 v1v2
v0v2 v0v1v2
京公网安备 11010502036488号