Floyd算法（完整版解决最短路径问题）
本文小述：本文运用邻接矩阵构造的是有向图，用邻接矩阵实现Floyd算法（有兴趣的话可以自己动手用邻接表的方法尝试实现以下），在实现的过程中加强了动态数组的运用。该代码配合 B站视频的讲解来看更易懂哦~代码是多注释、完整版（将.cpp和.h的文件代码联合起来便可完整实现）。
一、Floyd算法简介
Floyd（弗洛伊德）算法相对于Dijkstra算法来说，可以解决多源最短路径问题（即可以从任意一个点到任意一个点），可应用于地图导航走最短路径、为各城市修建最短路径的通信网（节省成本）等问题，时间复杂度是O(n3)
二、代码部分
知识储备：动态创建二维数组、邻接矩阵、图论、虚析构函数、静态函数（static）的运用
Graph.h文件代码
#ifndef GRAPH_H
#define GRAPH_H
#include <algorithm>
#include <stdio.h> // exit()函数需要用到的头文件
#define X 9999 //相当于无穷大
class Graph
{
private:
static Graph* instance; //创建实例：类是一个抽象类，实例可方便用于调取类成员的方法函数
int n, m; //n是顶点个数，m是边数
char* data; //顶点数组，用来储存顶点(char类型)
int** w; //weight 边的权重，邻接矩阵
int** path; //用来记录最小边权值顶点的序号，邻接矩阵
public:
Graph();
virtual ~Graph(); //虚析构函数，用来程序结束后释放new的内存
static Graph* getInstance(); //获取实例
void createGraph(Graph& G);
int getIndex(const Graph& G, char v); //获取顶点v的在顶点数组data中的下标
void Floyd(Graph& G);
void showPath(const Graph& G, int u, int v); //展示最短路径
};
#endif // GRAPH_H
自己在尝试写代码的时候，要弄清除一个图有哪些元素、一个算法需具备哪些元素，才有思路、好下手写代码喔~
Graph.cpp文件代码
#include "Graph.h"
#include <iostream>
using namespace std;
Graph::Graph() //默认构造
{
//ctor
}
Graph* Graph::instance = nullptr; //固定套路
Graph* Graph::getInstance() //同上，记住就好，也可以自己尝试理解下
{
if(!instance) instance = new Graph();
return instance;
}
int Graph::getIndex(const Graph& G, char v) //获取顶点v在顶点数组中的下标
{
for(int i = 0; i < G.n; i++)
if(G.data[i] == v) return i;
return -1; //没找到就返回-1
}
void Graph::createGraph(Graph& G)
{
cout << "please input the number of vertex and arc:";
cin >> G.n >> G.m;
G.data = new char[G.n]; //动态创建一维数组
cout << "please input the value of vertice:";
for(int p = 0; p < G.n; p++)
cin >> G.data[p];
char v1, v2;
int power, i, j;
G.w = new int*[G.n]; //动态创建二维数组，申请了 int* 类型的G.n行空间
for(int s = 0; s < G.n; s++)
G.w[s] = new int[G.n]; //每一行申请一个int类型的G.n列空间
for(int x = 0; x < G.n; x++)
for(int y = 0; y < G.n; y++){
if(x == y) G.w[x][y] = 0; //边的邻接矩阵中左对角线权重（即自己的权重）都设为0，因为是多源的
else G.w[x][y] = X; //其他边的权重初始化为无穷大
}
cout << "please input the weight of arc between 2 vertice as 100 A B:" << endl;
for(int k = 0; k < G.m; k++){
cin >> power >> v1 >> v2;
i = getIndex(G, v1);
j = getIndex(G, v2);
if(i == -1 || j == -1){ //没在顶点数组中找到对应的顶点下标
cout << "Sorry, I can't find the vertex" << endl;
exit(-1); //直接退出程序
}
G.w[i][j] = power; //有向图赋值边的权重
}
}
void Graph::Floyd(Graph& G)
{
G.path = new int*[G.n]; //动态创建二维数组
for(int s = 0; s < G.n; s++){
G.path[s] = new int[G.n];
for(int t = 0; t < G.n; t++)
G.path[s][t] = -1; //初始化path邻接矩阵的值
}
//特别注意：不能用fill函数来初始化动态二维数组，因为动态new出来的空间不一定连续
for(int v = 0; v < G.n; ++v) //v是指在某两个点中，它们之间点的下标
for(int i = 0; i < G.n; ++i)
for(int j = 0; j < G.n; ++j)
if(G.w[i][j] > G.w[i][v] + G.w[v][j]) //看配合B站视频讲解效果更棒，这里不多做解释！
{
G.w[i][j] = G.w[i][v] + G.w[v][j];
G.path[i][j] = v;
}
}
void Graph::showPath(const Graph& G, int u, int v)
{ //看配合B站视频讲解效果更棒，该函数不多做解释！
if(G.path[u][v] == -1) cout << G.data[u] << " to " << G.data[v] << endl; //B站输出的是顶点序号，我这输出的是顶点的值
else{
int mid = G.path[u][v];
showPath(G, u, mid);
showPath(G, mid, v);
}
}
Graph::~Graph() //虚析构函数作用：一般都是用来程序结束后释放new出来的内存
{
delete[] data;
for(int i = 0; i < n; i++)
delete[] w[i];
delete[] w;
for(int i = 0; i < n; i++)
delete[] path[i];
delete[] path;
}
其实我们在写算法的时候，无非就是对数据的储存进行操作（对二维数组的操作），这也是算法的本质。
main.cpp文件代码
#include <iostream>
#include "Graph.h" //自己写的头文件要用引号
using namespace std;
int main()
{
char v1, v2;
int a, b;
Graph G;
Graph::getInstance()->createGraph(G); //用实例来调取抽象类的函数方法
Graph::getInstance()->Floyd(G);
cout << "please input which two vertice you want to show the shortest path between them:";
cin >> v1 >> v2;
a = Graph::getInstance()->getIndex(G, v1);
b = Graph::getInstance()->getIndex(G, v2);
Graph::getInstance()->showPath(G, a, b);
return 0;
}
例子展示
Input(点我可进入链接