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");}簡單測試。
嗯 就醬紫