C语言接口实现弗洛伊德算法

本人第一次写，如有不足请多包涵！ <所有顶点对之间的最短路径 >

1.问 题 定 义

对于给定的有向网络G=(V,E)，要对G中任意两个顶点v,w（v≠w)，找出v到w的最短路径。

解决此问题的一种方法: （1.）轮流以每一个顶点为源点，重复执行迪杰斯特拉算法n次，即可求得每一对顶点之间的最短路径,总的时间复杂度为 （2.）弗洛伊德（Floyd）给出了一种更简洁的方法。【动态规划算法】

2.分析最优解的结构

最优子结构性质 子问题的重叠性

3.递归地定义最优解的代价

A(0)[i][j]=C[i][j] A(k)[i][j]= min{A(k-1)[i][j] , A(k-1)[i][k]+A(k-1)[k][j]} (1≤k≤n) 其中C矩阵是图的矩阵。

4.递归地划分问题，直至不分

A(n)[i][j] (1≤i, j≤n) A(n-1)[i][j] (1≤i, j≤n) … … … … A(1)[i][j] (1≤i, j≤n) A(0)[i][j] (1≤i, j≤n)

5.自底向上求解各个子问题

算法实现代码：

我代码实现用的是C语言接口方法，虽然感觉比普通方法可能麻烦一点，我的目的是锻炼自己使用接口。这样既能锻炼自己使用接口也能实现弗洛伊德算法。 整个程序由三个文件组成： Floyd.h 定义数据结构并为用户接口提供原型。 Floyd.c 提供函数代码以实现实现接口。 UseFloyd.c 将列表接口应用于具体编程问题的源代码文件 首先是 Floyd.h文件中函数声明部分

#ifndef _FLOYD_H #define _FLOYD_H #define MAX 5 typedef struct { int edges[MAX][MAX];//邻接矩阵 int n, e;//顶点数和边数 }Mgraph; void Creatgraph(Mgraph *pg);//创建图 void PrintGraph(Mgraph *pg, int path[][MAX]);//打印创建的邻接矩阵A[i][j]和path[i][j] void Floyd(Mgraph *pg, int A[][MAX], int path[][MAX]);//弗洛伊德算法 void Printpath(Mgraph *pg,int A[][MAX], int path[][MAX]);//打印求好的A[i][j]和path[i][j]以及各个节点最短路径 #endif

Floyd.c函数定义部分

#include<stdio.h> #include "Floyd.h" void Creatgraph(Mgraph *pg) { puts("请输入顶点数"); scanf("%d", &pg->n); puts("请输入边数"); scanf("%d", &pg->e); for (int i = 0; i < pg->n; i++)//for循环里是初始化图 { for (int j = 0; j < pg->n; j++) { if (i == j) pg->edges[i][j] = 0; else pg->edges[i][j] = 888;//用888代替无穷大 } } puts("请输入个顶点之间的路径长度如（v1 v2 5:）"); int i, j,pz; for (int k = 0; k < pg->e; k++) { puts("请输入...."); scanf("%d %d %d", &i, &j, &pz); pg->edges[i][j] = pz;//这里用节点编号减一对应矩阵的i和j } puts("输入完毕！..."); } void PrintGraph(Mgraph *pg, int path[][MAX])//打印创建好的邻接矩阵A和path { path[MAX][MAX] = { 0 }; for (int i = 0; i < pg->n; i++)//初始化path矩阵 { for (int j = 0; j < pg->n; j++) { if (pg->edges[i][j] != 888) path[i][j] = j+1; } } puts("A[i][j]"); for (int i = 0; i < pg->n; i++)//打印邻接矩阵A { for (int j = 0; j < pg->n; j++) printf("]", pg->edges[i][j]); puts(""); } puts("path[i][j]"); for (int i = 0; i < pg->n; i++)//打印path矩阵 { for (int j = 0; j < pg->n; j++) printf("]",path[i][j]); puts(""); } } void Floyd(Mgraph *pg, int A[][MAX], int path[][MAX])//弗洛伊德算法 { for (int i = 0; i <pg->n; i++) { for (int j = 0; j < pg->n; j++) A[i][j] = pg->edges[i][j]; } for (int k = 0; k < pg->n; k++) for (int i = 0; i < pg->n; i++) for (int j = 0; j < pg->n;j++) if (A[i][j]>A[i][k]+A[k][j]) { A[i][j] = A[i][k] + A[k][j]; path[i][j] = k + 1; } } void Printpath(Mgraph *pg,int A[][MAX], int path[][MAX])//打印求好的A和path以及最短路径 { puts("A[i][j]:"); for (int i = 0; i < pg->n; i++) //打印邻接矩阵A { for (int j = 0; j < pg->n; j++) printf("]", A[i][j]); puts(""); } puts("path[i][j]:"); for (int i = 0; i < pg->n; i++)//打印path矩阵 { for (int j = 0; j < pg->n; j++) printf("]", path[i][j]); puts(""); } int next; for (int i = 0; i <pg->n; i++)//求最短路径并打印 { for (int j = 0; j < pg->n; j++) { next = path[i][j]; if (next==0) printf("%d到%d之间没有路径！\n", i + 1, j + 1); else { printf("%d", i + 1); while (next!=j+1) { printf("-->%d", next); next = path[next - 1][j]; } printf("-->%d\n", j + 1); } } } }

UseFloyd.c测试部分

#include<stdio.h> #include "Floyd.h" int main() { int path[MAX][MAX] = {0}; Mgraph tu; puts("创建图"); Creatgraph(&tu); puts("输出图"); PrintGraph(&tu, path); int A[MAX][MAX] = { 0 }; Floyd(&tu, A, path); puts("打印结果..."); Printpath(&tu,A, path); return 0; }

运行结果 首先输入顶点数和边数，有路径的两个节点，以及有路径的两个节点之间长度 输出初始化的A和path（用888代替无穷大） 输出经过弗洛伊德算法运算过后的A和path 打印各个节点之间的最短路径 代码运行的总体部分 本人第一次写博客如有不足还请多指教，本人知识有限，可能程序有点臃肿，希望见谅，以后一点会好好改善的。