Floyd算法 有向图。

Floyd算法求所有点之间的最短路 可以有负权值  时间复杂度O(n^3）

用的是邻接矩阵

从 i 到 j 两个点之间。。假设最短路径是 D i j  如果从i到中间任意点k   D i k +D k j这个距离小于了假设的这个D ij 那就把Di j 替换为D i k+D k j

用三个for

第一个 每一个点都要把所有点当做一次k点 进行刚刚说的比较

第二个 代表 i 开始的点

第三个 代表 j 结束的点  i j 就遍历了所有点

 for (int k = 1; k <= n; k++)       for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++){if (edge[i][k] + edge[k][j] < edge[i][j])edge[i][j] = edge[i][k] + edge[k][j] ; //对于所有i j 都处理一次 完了edge[i][j]存储的就是两点之间的最短路了}

贴个用过的完整马。就水数据跑了一下

#include <iostream>using namespace std;struct Graph{	char v[555];	int  edge[555][555];	int n, e;};class A{public:	explicit A(int m,int n);	~A();	void Floyd();PRivate:	Graph *G;};A::A(int m, int num){	G = new Graph;	G->n = m;	G->e = num;		for (int i = 0; i < G->n;i++)	{				cout << "Input a char as Node/n";		char a;		cin >> a;		G->v[i] = a;			}	for (int i = 0; i <= G->n; i++)	{				for (int j = 0; j <= G->n; j++)			G->edge[i][j] = 9999999;		G->edge[i][i] = 0;	}	for (int i = 0; i < G->e; i++)	{		cout << "Input i j w/n";		int egi;		int egj;		int w;		cin >> egi >> egj >> w;		G->edge[egi][egj] = w;			}	}A::~A(){	delete G;}void A::Floyd(){	for (int k = 1; k <= G->n; k++)		for (int i = 1; i <= G->n; i++)			for (int j = 1; j <= G->n; j++)			{				if (G->edge[i][k] + G->edge[k][j] < G->edge[i][j])					G->edge[i][j] = G->edge[i][k] + G->edge[k][j];			}	cout << G->edge[1][2] << endl;	cout << G->edge[1][3] << endl;	cout << G->edge[2][3] << endl;	}
#include "h.h"int main(){	A a(3, 5);	a.Floyd();	system("pause");}简单测试。
嗯 就酱紫