弗洛伊德算法，是一種用于尋找圖形中所有最短路徑的算法。它的基本思想是通過一定的規(guī)則逐步更新每個(gè)節(jié)點(diǎn)的最短路徑估計(jì)值，直到每個(gè)節(jié)點(diǎn)的最短路徑估計(jì)值收斂為止。

具體來說，弗洛伊德算法通過求解所有點(diǎn)對之間的最短路徑來實(shí)現(xiàn)。在算法開始時(shí)，我們假設(shè)圖中的所有節(jié)點(diǎn)之間都是不聯(lián)通的，即它們之間的距離為無窮大。然后，我們對圖進(jìn)行“松弛”操作，即嘗試更新每個(gè)節(jié)點(diǎn)之間的距離估計(jì)值，以尋找更短的路徑。具體來說，對于圖中的每個(gè)節(jié)點(diǎn)對(i,j)，我們檢查是否存在一個(gè)節(jié)點(diǎn)k，使得從i到k再到j(luò)的路徑比已知的最短路徑更短。如果是的話，我們就更新(i,j)之間的距離估計(jì)值為更短的路徑長度。

通過重復(fù)這個(gè)過程，我們最終得到了圖中所有節(jié)點(diǎn)之間的最短路徑估計(jì)值。弗洛伊德算法的時(shí)間復(fù)雜度為O(n^3)，其中n是圖中節(jié)點(diǎn)的數(shù)量。

鄰接矩陣為

弗洛伊德算法

每次都選一個(gè)頂點(diǎn)作為中轉(zhuǎn)點(diǎn)

第一次將V0作為中轉(zhuǎn)點(diǎn)

對所有頂點(diǎn)i,j做判斷dist[i][j]>dist[i][k]+dist[k][j] （k為此時(shí)的中轉(zhuǎn)點(diǎn)）

第二次將V1作為中轉(zhuǎn)點(diǎn)

再次對所有頂點(diǎn)i,j做判斷dist[i][j]>dist[i][k]+dist[k][j] （k為此時(shí)的中轉(zhuǎn)點(diǎn)）

第三次將V2作為中轉(zhuǎn)點(diǎn)

對所有頂點(diǎn)i,j做判斷dist[i][j]>dist[i][k]+dist[k][j] （k為此時(shí)的中轉(zhuǎn)點(diǎn)）

就得到了最終結(jié)果

下面我們來看一下代碼是如何實(shí)現(xiàn)的（c語言代碼實(shí)現(xiàn)）

void floyd(int graph[n][n])//弗洛伊德求各頂點(diǎn)之間的最短路徑
{
	int dist[n][n];
	for (int i = 0; i < n; i++)//初始化距離矩陣
	{
		for (int j = 0; j < n; j++)
			dist[i][j] = graph[i][j];
	}
	for (int k = 0; k < n; k++)//逐一考慮每個(gè)頂點(diǎn)作為中間頂點(diǎn)
	{
		for (int i = 0; i < n; i++)//
		{
			for (int j = 0; j < n; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])//k作為中間頂點(diǎn)，可以縮短（i，j）的距離
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dist[i][j] != Max)
				printf("%d\t", dist[i][j]);
			else
				printf("Max");
		}
		printf("\n");
	}
}

完整測試代碼

#include<stdio.h>
#define Max 0xFFFF
#define n 3
void floyd(int graph[n][n])//弗洛伊德求各頂點(diǎn)之間的最短路徑
{
	int dist[n][n];
	for (int i = 0; i < n; i++)//初始化距離矩陣
	{
		for (int j = 0; j < n; j++)
			dist[i][j] = graph[i][j];
	}
	for (int k = 0; k < n; k++)//逐一考慮每個(gè)頂點(diǎn)作為中間頂點(diǎn)
	{
		for (int i = 0; i < n; i++)//
		{
			for (int j = 0; j < n; j++)
			{
				if (dist[i][j] > dist[i][k] + dist[k][j])//k作為中間頂點(diǎn)，可以縮短（i，j）的距離
					dist[i][j] = dist[i][k] + dist[k][j];
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (dist[i][j] != Max)
				printf("%d\t", dist[i][j]);
			else
				printf("Max");
		}
		printf("\n");
	}
}
int main()
{
	int graph[n][n] = { {0,6,13},{10,0,4} ,{5,Max,0} };
	floyd(graph);
	return 0;
}

?文章來源地址http://www.zghlxwxcb.cn/news/detail-713254.html

到了這里，關(guān)于弗洛伊德（Floyd）算法求個(gè)頂點(diǎn)之間最短路徑問題（詳解+圖解）的文章就介紹完了。如果您還想了解更多內(nèi)容，請?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！