最短路径——floyd（多源最短路径）

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <queue>

#include <malloc.h>

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(n)

测试及结果：