多源最短路径（Floyed）
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
class Graph{
private:
int vertex; //顶点数
//int** matrix; //有向图关系矩阵
int** path; //存储关系矩阵
int** pre; //存储中间节点k
public:
const int maxium = 10000; //最大值，表示不存在的边
Graph(const int edges, const int nodes, int arr[][3]){
vertex = nodes;
//matrix = new int* [vertex]; //生成有向图关系矩阵
pre = new int* [vertex];
path = new int* [vertex]; //生成有向图关系矩阵
for (int i=0; i<vertex; ++i){
pre[i] = new int[vertex];
path[i] = new int[vertex];
//matrix[i] = new int[vertex];
for (int j=0; j<vertex; j++){
//matrix[i][j] = maxium;
path[i][j] = maxium;
pre[i][j] = -1;
}
}
for (int i=0; i<edges; ++i){ //生成有向图关系,maxium为不连接
//matrix[arr[i][0]][arr[i][1]] = arr[i][2];
path[arr[i][0]][arr[i][1]] = arr[i][2];
}
}
~Graph(){
delete[] path;
//delete[] matrix;
delete[] pre;
}
void floyd(int s, int end){
for (int k=0; k<vertex; ++k){ //中间点更新
for (int i=0; i<vertex; ++i){ //起点
for (int j=0; j<vertex; ++j){ //终点
if (path[i][k] + path[k][j] < path[i][j]){
path[i][j] = path[i][k] + path[k][j];
pre[i][j] = k;
}
}
}
}
show(s, end);
}
void show(int start, int end){ //显示路径,单源，多源直接for循环调用这个函数
int k = pre[start][end];
if (k != -1){
show(start, k);
cout << k << " ";
show(k, end);
}
}
};
int main(){
int arr[][3] = {{0,1,8},{0,3,16,},{0,4,7},{1,3,9},{1,5,5},{2,9,2},
{3,2,1},{3,6,10},{3,8,12},{4,7,5},{4,3,9},{4,8,7},{5,3,2},
{5,2,11},{6,2,13},{6,9,2},{7,6,8},{8,7,1},{8,6,6}};//创建一个有向权值图，每一列分别对应起点，终点，权值
Graph t(19, 10, arr);
t.floyd(0, 9);
return 0;
}