图的Floyd算法——C/C++

╰+攻爆jí腚メ 2021-12-22 23:13 194阅读 0赞

例子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]

## 一、算法原理 ##

1.  通过一个图的权值矩阵求出它的每两点间的最短路径矩阵。
2.  从图的带权邻接矩阵A=\[a(i,j)\]，n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一个公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短路径长度，称D(n)为图的距离矩阵，同时还可引入一个后继节点矩阵path来记录两点间的最短路径。
3.  采用松弛技术（松弛操作），对在i和j之间的所有其他点进行一次松弛。所以时间复杂度为O(n^3);

## 二、算法思想 ##

**1. 从任意一条单边路径开始。所有两点之间的距离是边的权，如果两点之间没有边相连，则权为无穷大。**  
**2. 对于每一对顶点 u 和v，看看是否存在一个顶点 w 使得从 u 到 w 再到 v 比已知的路径更短。如果是更新它。**  
3. 把图用邻接矩阵G表示出来，如果从Vi到Vj有路可达，则G\[i\]\[j\]=d，d表示该路的长度；否则G\[i\]\[j\]=无穷大。定义一个矩阵D用来记录所插入点的信息，D\[i\]\[j\]表示从Vi到Vj需要经过的点，初始化D\[i\]\[j\]=j。把各个顶点插入图中，比较插点后的距离与原来的距离，G\[i\]\[j\]= min( G\[i\]\[j\], G\[i\]\[k\]+G\[k\]\[j\] )，如果G\[i\]\[j\]的值变小，则D\[i\]\[j\]=k。在G中包含有两点之间最短道路的信息，而在D中则包含了最短通路径的信息。  
4. 比如，要寻找从V5到V1的路径。根据D，假如D(5,1)=3则说明从V5到V1经过V3，路径为\{V5,V3,V1\}，如果D(5,3)=3，说明V5与V3直接相连，如果D(3,1)=1，说明V3与V1直接相连。

## 三、算法实现 ##

**1、Floyd算法**

void Floyd(MatGraph MG) {
    	int i, j, k;
    	int A[MAXV][MAXV];
    	int path[MAXV][MAXV];
    	for (i = 0; i < MG.n; i++) {
    		for (j = 0; j < MG.n; j++) {
    			A[i][j] = MG.adjMat[i][j];
    			if (i != j && MG.adjMat[i][j] < INF) {
    				path[i][j] = i;							//顶点 i 到顶点 j 有边时
    			}
    			else {
    				path[i][j] = -1;						//顶点 i 到顶点 j 无边时
    			}
    		}
    	}
    	for (k = 0; k < MG.n; k++) {						//一次考察所有顶点
    		for (i = 0; i < MG.n; i++) {
    			for (j = 0; j < MG.n; j++) {
    				if (A[i][j] > A[i][k] + A[k][j]) {
    					A[i][j] = A[i][k] + A[k][j];		//修改最短路径长度
    					path[i][j] = path[k][j];			//修改最短路径
    				}
    			}
    		}
    	}
    	displayPath(MG, A, path);							//输出最短路径
    }

**2、输出多源最短路径**

void displayPath(MatGraph MG, int A[MAXV][MAXV], int path[MAXV][MAXV]) {
    	int i, j, k;
    	int s;
    	int aPath[MAXV];										//存放一条最短路径（逆向）
    	int d;													//顶点个数
    	for (i = 0; i < MG.n; i++) {
    		for (j = 0; j < MG.n; j++) {
    			if (A[i][j] != INF && i != j) {					//若顶点 i 和 顶点 j 之间存在路径
    				printf("从 %d 到 %d 的路径为：", i, j);
    				k = path[i][j];
    				d = 0;
    				aPath[d] = j;								//路径上添加终点
    				while (k != -1 && k != i) {					//路劲上添加中间点
    					d++;
    					aPath[d] = k;
    					k = path[i][k];
    				}
    				d++;
    				aPath[d] = i;								//路径上添加起点
    				printf("%d", aPath[d]);						//输出起点
    				for (s = d - 1; s >= 0; s--) {				//输出路径上其他顶点
    					printf("->%d", aPath[s]);
    				}
    				printf("\t\t");
    				printf("路径长度为：%d\n", A[i][j]);
    			}
    		}
    	}
    }

## 四、整体框架 ##

#include<stdio.h>
    #include<malloc.h>
    
    #define MAXV 7					//最大顶点个数 
    #define INF 32767				//定义 ∞
    //∞ == 32767 ,int 型的最大范围（2位）= 2^(2*8-1)，TC告诉我们int占用2个字节，而VC和LGCC告诉我们int占用4个字节
    //图：Graph
    //顶点：Vertex
    //邻接：Adjacency
    //矩阵：Matrix
    //表：List
    //边：Edge 
    
    typedef struct vertex {
    	int number;					//顶点的编号 	
    }VertexType; 					//别名，顶点的类型 
    
    typedef struct matrix {
    	int n;						//顶点个数
    	int e;						//边数 
    	int adjMat[MAXV][MAXV];		//邻接矩阵数组			
    	VertexType ver[MAXV];		//存放顶点信息 
    }MatGraph;						//别名，完整的图邻接矩阵类型
    
    typedef struct eNode {
    	int adjVer;					//该边的邻接点编号 
    	int weiLGht;				//该边的的信息，如权值 
    	struct eNode* nextEdLGe;	//指向下一条边的指针 
    }EdgeNode; 						//别名，边结点的类型 
    
    typedef struct vNode {
    	EdgeNode* firstEdLGe;		//指向第一个边结点 
    }VNode; 						//别名，邻接表的头结点类型 
    
    typedef struct list {
    	int n;						//顶点个数
    	int e;						//边数
    	VNode adjList[MAXV];		//邻接表的头结点数组 
    }ListGraph;						//别名，完整的图邻接表类型 
    
    //创建图的邻接表 
    void createAdjListGraph(ListGraph*& LG, int A[MAXV][MAXV], int n, int e) {
    	int i, j;
    	EdgeNode* p;
    	LG = (ListGraph*)malloc(sizeof(ListGraph));
    	for (i = 0; i < n; i++) {
    		LG->adjList[i].firstEdLGe = NULL;						//给邻接表中所有头结点指针域置初值 
    	}
    	for (i = 0; i < n; i++) {									//检查邻接矩阵中的每个元素 
    		for (j = n - 1; j >= 0; j--) {
    			if (A[i][j] != 0) {									//存在一条边 
    				p = (EdgeNode*)malloc(sizeof(EdgeNode));		//申请一个结点内存
    				p->adjVer = j;									//存放邻接点 
    				p->weiLGht = A[i][j];							//存放权值
    				p->nextEdLGe = NULL;
    
    				p->nextEdLGe = LG->adjList[i].firstEdLGe;		//头插法 
    				LG->adjList[i].firstEdLGe = p;
    			}
    		}
    	}
    	LG->n = n;
    	LG->e = e;
    }
    
    //输出邻接表 
    void displayAdjList(ListGraph* LG) {
    	int i;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {
    		p = LG->adjList[i].firstEdLGe;
    		printf("%d:", i);
    		while (p != NULL) {
    			if (p->weiLGht != 32767) {
    				printf("%2d[%d]->", p->adjVer, p->weiLGht);
    			}
    			p = p->nextEdLGe;
    		}
    		printf(" NULL\n");
    	}
    }
    
    //输出邻接矩阵
    void displayAdjMat(MatGraph MG) {
    	int i, j;
    	for (i = 0; i < MAXV; i++) {
    		for (j = 0; j < MAXV; j++) {
    			if (MG.adjMat[i][j] == 0) {
    				printf("%4s", "0");
    			}
    			else if (MG.adjMat[i][j] == 32767) {
    				printf("%4s", "∞");
    			}
    			else {
    				printf("%4d", MG.adjMat[i][j]);
    			}
    		}
    		printf("\n");
    	}
    }
    
    //邻接表转换为邻接矩阵
    void ListToMat(ListGraph* LG, MatGraph& MG) {
    	int i, j;
    	EdgeNode* p;
    	for (i = 0; i < MAXV; i++) {
    		for (j = 0; j < MAXV; j++) {
    			MG.adjMat[i][j] = 0;
    		}
    	}
    	for (i = 0; i < LG->n; i++) {
    		p = LG->adjList[i].firstEdLGe;
    		while (p != NULL) {
    			MG.adjMat[i][p->adjVer] = p->weiLGht;
    			p = p->nextEdLGe;
    		}
    	}
    	MG.n = LG->n;
    	MG.e = LG->e;
    }
    
    //输出多源最短路径
    void displayPath(MatGraph MG, int A[MAXV][MAXV], int path[MAXV][MAXV]) {
    	int i, j, k;
    	int s;
    	int aPath[MAXV];										//存放一条最短路径（逆向）
    	int d;													//顶点个数
    	for (i = 0; i < MG.n; i++) {
    		for (j = 0; j < MG.n; j++) {
    			if (A[i][j] != INF && i != j) {					//若顶点 i 和 顶点 j 之间存在路径
    				printf("从 %d 到 %d 的路径为：", i, j);
    				k = path[i][j];
    				d = 0;
    				aPath[d] = j;								//路径上添加终点
    				while (k != -1 && k != i) {					//路劲上添加中间点
    					d++;
    					aPath[d] = k;
    					k = path[i][k];
    				}
    				d++;
    				aPath[d] = i;								//路径上添加起点
    				printf("%d", aPath[d]);						//输出起点
    				for (s = d - 1; s >= 0; s--) {				//输出路径上其他顶点
    					printf("->%d", aPath[s]);
    				}
    				printf("\t\t");
    				printf("路径长度为：%d\n", A[i][j]);
    			}
    		}
    	}
    }
    
    //Floyd算法
    void Floyd(MatGraph MG) {
    	int i, j, k;
    	int A[MAXV][MAXV];
    	int path[MAXV][MAXV];
    	for (i = 0; i < MG.n; i++) {
    		for (j = 0; j < MG.n; j++) {
    			A[i][j] = MG.adjMat[i][j];
    			if (i != j && MG.adjMat[i][j] < INF) {
    				path[i][j] = i;							//顶点 i 到顶点 j 有边时
    			}
    			else {
    				path[i][j] = -1;						//顶点 i 到顶点 j 无边时
    			}
    		}
    	}
    	for (k = 0; k < MG.n; k++) {						//一次考察所有顶点
    		for (i = 0; i < MG.n; i++) {
    			for (j = 0; j < MG.n; j++) {
    				if (A[i][j] > A[i][k] + A[k][j]) {
    					A[i][j] = A[i][k] + A[k][j];		//修改最短路径长度
    					path[i][j] = path[k][j];			//修改最短路径
    				}
    			}
    		}
    	}
    	displayPath(MG, A, path);							//输出最短路径
    }
    
    int main() {
    	ListGraph* LG;
    	MatGraph MG;
    
    	int array[MAXV][MAXV] = {
    		{  0,  4,  6,  6,INF,INF,INF},
    		{INF,  0,  1,INF,  7,INF,INF},
    		{INF,INF,  0,INF,  6,  4,INF},
    		{INF,INF,  2,  0,INF,  5,INF},
    		{INF,INF,INF,INF,  0,INF,  6},
    		{INF,INF,INF,INF,  1,  0,  8},
    		{INF,INF,INF,INF,INF,INF,  0}
    	};
    
    	int e = 12;
    	createAdjListGraph(LG, array, MAXV, e);
    	displayAdjList(LG);
    	printf("\n");
    
    	ListToMat(LG, MG);
    	displayAdjMat(MG);
    	printf("\n");
    
    	Floyd(MG);
    	printf("\n");
    
    	return 0;
    }

## 五、结果展示 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70]: /images/20211220/4c6ba1bd502a48d6bb7d67812e8c0889.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjEwOTAxMg_size_16_color_FFFFFF_t_70 1]: /images/20211220/4574f87c100e433994f1dd9b4b631d85.png