#include#include #include #include #include #include using namespace std;const int VERTEX_NUM = 20;const int INFINITY = 0x7fffffff;bool vis[VERTEX_NUM];int dist[VERTEX_NUM][VERTEX_NUM]; class Graph {public: int vexNum; int edgeNum; int vex[VERTEX_NUM]; int arc[VERTEX_NUM][VERTEX_NUM]; };void createGraph(Graph &G){ cout << "please input vexNum and edgeNum: "; cin >> G.vexNum >> G.edgeNum; for (int i = 0; i != G.vexNum; ++i) { cout << "please input no" << i+1 << " vertex: "; cin >> G.vex[i]; // 自定义顶点序号 } for (int i = 0; i != G.vexNum; ++i) { for (int j = 0; j != G.vexNum; ++j) { if (i == j) G.arc[i][j] = 0; else G.arc[i][j] = INFINITY; } } for (int k = 0; k != G.edgeNum; ++k) { cout << "please input the vertex of edge(vi, vj) and weight: "; int i, j, w; cin >> i >> j >> w; G.arc[i][j] = w; G.arc[j][i] = G.arc[i][j]; }}// Floyd算法 void floyd(Graph &G){ memset(dist, INFINITY, VERTEX_NUM); for (int k = 0; k != G.vexNum; ++k) { for (int i = 0; i != G.vexNum; ++i) { for (int j = 0; j != G.vexNum; ++j) { if (G.arc[i][j] > G.arc[i][k] + G.arc[k][j] && G.arc[i][k] < INFINITY && G.arc[k][j] < INFINITY) { G.arc[i][j] = G.arc[i][k] + G.arc[k][j]; } } } }}int main(){ Graph G; createGraph(G); floyd(G); for (int i = 0; i != G.vexNum; ++i) { for (int j = 0; j != G.vexNum; ++j) { if (i == j) continue; cout << "源点" << i << "到点" << j << "的距离为" << G.arc[i][j] << endl; } } return 0;}
时间复杂度：O(n3)
测试及结果：
