算法的思想:
遍历每个结点. 然后以这个结点为中间结点来更新所有的结点.
edge(I,j) = min( edge( I , k ) + edge( k , j ) , edge( I , j ) )
edge 就是边的长度
例如:
首先 以 1 为中间结点, 更新(1,2),(1,3)(1,4)(1,5)(1,6)(2,3)(2,4)...... 等所有结点
其次, 在以 2 为中间结点, 更新(1,2),(1,3)(1,4)(1,5)(1,6)(2,3)(2,4)...... 等所有结点
再者, 在以 3 为中间结点, 更新(1,2),(1,3)(1,4)(1,5)(1,6)(2,3)(2,4)...... 等所有结点
以至于后面所有的结点.
在这里需要用到一个数组来记录前继结点.
这个算法的主要形式就是三层循环. 从外到内在这里依次为一, 二, 三, 层循环.
第一层循环是中间结点.
第二层循环 0 是起始结点
第三层循环是结束结点.
需要定义一个 path[][]数组. 初始化为每对结点的终止结点, 例如 (i,j) 那就在 i,j 对应的 path 数组中对应的值为 j.
初始化 path 数组如下:
三层循环如下:
代码如下;
- //
- // main.cpp
- // Floyd
- //
- // Created by 橘子和香蕉 on 2018/12/15.
- // Copyright © 2018 橘子和香蕉 All rights reserved.
- //
- /*
- 1: 求各个顶点之间的最短路径 时间复杂度是 n*3
- 2: 从图的邻接矩阵出发,
- 还是和之前的算法一样, 找一个中间结点来更新所有的结点. 假如 v 到 u 最短距离, 还有几个结点, 比如是 m,n,b
- 遍历这个结点, 比如现在用 m 来更新所有的结点, 看距离是不是短的, 要是比之前短, 就更新, 否则, 就不要更新,
- 就是. D(u,v) = min(D(u,v),D(u,m)+D(m,v))
- 这个算法三层循环, 中间结点在最外面的一层. 因为这样的才可以以他为中心, 来遍历所有的结点
- */
- #include <iostream>
- using namespace std;
- #define VERTEXNUM 100
- #define INT_MAX 9999
- class Graph{
- private:
- char vertex[VERTEXNUM];// 顶点表
- int edge[VERTEXNUM][VERTEXNUM];// 边表
- int vertexNum;// 顶点个数
- int edgeNum;// 边的个数
- int locate(char data);// 在顶点表中找 data 的位置
- void initEdge();
- public:
- Graph(int vertexNum,int edgeNum);
- void create();
- void Floyd(char start ,char end);
- void printGraph();// 输出
- };
- void Graph::printGraph(){
- cout<<endl;
- cout<<endl;
- cout<<"顶点边:\n";
- cout<<"vertexNum:"<<vertexNum<<"edgeNum:"<<edgeNum<<endl;
- for (int i = 0; i<vertexNum; i++) {
- cout<<vertex[i]<<"\t";
- }
- cout<<endl;
- cout<<"边表如下:\n";
- for (int j = 0; j<vertexNum; j++) {
- for (int k = 0; k<vertexNum ; k++) {
- cout<<edge[j][k]<<"\t";
- }
- cout<<endl;
- }
- }
- int Graph::locate(char data){
- for (int i = 0; i<vertexNum;i++) {
- if(vertex[i] == data){
- return I;
- }
- }
- return -1;
- }
- Graph::Graph(int vertexNum,int edgeNum){
- this->vertexNum = vertexNum;
- this->edgeNum = edgeNum;
- initEdge();
- }
- void Graph::create(){
- cout<<"input Graph data\n";
- for (int i = 0; i<vertexNum; i++) {
- cin>>vertex[I];
- }
- char start ,end;
- int wieght = -1;
- for (int j = 0; j<edgeNum; j++) {
- cout<<"input start and end of edge:\n";
- cin>>start>>end>>wieght;
- int startPosition = locate(start);
- int endPosition = locate(end);
- edge[startPosition][endPosition] = wieght;
- edge[endPosition][startPosition] = wieght;
- }
- }
- void Graph:: initEdge(){
- for (int i = 0; i<vertexNum; i++) {
- for (int j =0 ; j<=i; j++) {
- edge[i][j] = INT_MAX;
- edge[j][i] = INT_MAX;
- }
- }
- for (int i = 0; i<vertexNum; i++) {
- for (int j = 0; j<vertexNum; j++) {
- cout<<edge[i][j]<<"\t";
- }
- cout<<endl;
- }
- }
- void Graph::Floyd(char start,char end){
- int path[vertexNum][vertexNum];// 定义路径数组
- for (int i = 0; i<vertexNum; i++) {// 初始化, 默认 i 到 j 的中间结点是 j
- for (int j = 0; j<vertexNum; j++) {
- path[i][j] = j;
- }
- }
- for (int k = 0; k <vertexNum; k++) {
- for (int i = 0; i < vertexNum; i++) {
- for (int j = 0; j < vertexNum; j++) {
- if( edge[i][k]+edge[k][j] < edge[i][j]){
- edge[i][j] = edge[i][k]+edge[k][j];
- path[i][j] = path[i][k];
- }
- }
- }
- }
- cout<<"每一对顶点的路径如下";
- int k = -1;
- for (int i = 0; i < vertexNum; i++) {
- for (int j = i+1; j < vertexNum; j++) {
- cout<<"<"<<vertex[i]<<":"<<vertex[j]<<">\t";
- k = path[i][j];
- cout<<vertex[i]<<"\t";
- while (k != j) {
- cout<<vertex[k]<<"\t";
- k = path[k][j];
- }
- cout<<endl;
- }
- }
- cout<<endl;
- cout<<"path 如下 \ n";
- for (int i = 0; i <vertexNum; i++) {
- for (int j = 0; j < vertexNum; j++) {
- cout<<path[i][j]<<"\t";
- }
- cout<<endl;
- }
- cout<<"要查找的"<<start<<"到"<<end<<"的路径如下 \ n";
- int startPosition = locate(start);
- int endPosition = locate(end);
- cout<<"<"<<start<<":"<<end<<">\t"<<start<<"\t";
- k = path[startPosition][endPosition];
- while (k != endPosition) {
- cout<<vertex[k]<<"\t";
- k = path[k][endPosition];
- }
- }
- int main(){
- Graph a(6, 8);
- a.create();
- a.printGraph();
- a.Floyd('1', '2');
- }
path 数组中保存的是前一个结点的位置
那怎么输出呢?
如下所示:
测试的时候是上面的图.
例如要查找 1 到 2 的对应的最短路径
先去查找 path 数组中, 1 ,2 对应的值, 结果是 4, 这就说明 4 是第一个中间结点, 继续查找 path 中, 4,2 对应的项, 发现是 3, 这就说明 3 是 2 到 4 的中间结点. 也就是 1 到 2 的第二个中间结点, 继续查找 3 到 2 在 path 对应的项, 发现是 2, 这就说明没有中间结点了.
输出代码如下:
这里的图的无向带权图, 代码运行结果如下;
来源: https://yq.aliyun.com/articles/679719