C++的最短路徑的弗洛伊德算法案例講解

更新時(shí)間：2021年08月16日 15:20:57 作者：riba2534

這篇文章主要介紹了C++的最短路徑的弗洛伊德算法案例講解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下

現(xiàn)在我們有這么一張圖：

我們要做的是求出從某一點(diǎn)到達(dá)任意一點(diǎn)的最短距離，我們先用鄰接矩陣來建圖，map[i][j]表示從i點(diǎn)到j(luò)點(diǎn)的距離，把自己到自己設(shè)為0，把自己到不了的邊初始化為無窮大，代碼為：

//初始化
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=inf;
    //讀入邊
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&t1,&t2,&t3);
        map[t1][t2]=t3;
    }

最后，建好的圖可以用表格來表示：

現(xiàn)在，我們來思考，假設(shè)我們來找一個(gè)中轉(zhuǎn)的點(diǎn)，看他們的路程會(huì)不會(huì)改變，我們先以1號(hào)頂點(diǎn)作為中轉(zhuǎn)點(diǎn)最為例子，制圖：

我們發(fā)現(xiàn)，圖有了變化，我們?cè)趺磁袛嘁?號(hào)頂點(diǎn)作為中轉(zhuǎn)點(diǎn)圖的路程是不是更短呢，我們只需要判斷map[i][1]+map[1][j]的路程是不是比map[i][j]的路程更短，就可以判斷，

代碼為：

for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        if(map[i][1]+map[1][j]<map[i][j])
            map[i][j]=map[i][1]+map[1][j];

現(xiàn)在該怎么辦呢，我們接著以2號(hào)頂點(diǎn)作為中轉(zhuǎn)點(diǎn)，很簡(jiǎn)單代碼修改一句就就可以：

for(int i=1; i<=n; i++)
    for(int j=1; j<=n; j++)
        if(map[i][2]+map[2][j]<map[i][j])
            map[i][j]=map[i][2]+map[2][j];

現(xiàn)在我們是不是發(fā)現(xiàn)了一個(gè)規(guī)律，只要不斷的遍歷每一個(gè)點(diǎn)，并且以每一個(gè)點(diǎn)作為中轉(zhuǎn)點(diǎn)看看它的值會(huì)不會(huì)改變，就可以得到從一個(gè)點(diǎn)到任意一個(gè)點(diǎn)的最短路徑，也就是多源最短路，這就是弗洛伊德算法，代碼為：

for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(map[i][k]+map[k][j]<map[i][j])
                map[i][j]=map[i][k]+map[k][j];

這樣就可以遍歷每個(gè)頂點(diǎn)，找出所有的最短路，算法的復(fù)雜度為O(n^3).

對(duì)于我一開始提出的問題，完整的代碼為：

#include <stdio.h>
#include <string.h>
#include <string>
#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int inf=1<<29;
int main()
{
    int map[10][10],n,m,t1,t2,t3;
    scanf("%d%d",&n,&m);//n表示頂點(diǎn)個(gè)數(shù)，m表示邊的條數(shù)
    //初始化
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            if(i==j)
                map[i][j]=0;
            else
                map[i][j]=inf;
    //讀入邊
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d%d",&t1,&t2,&t3);
        map[t1][t2]=t3;
    }
    //弗洛伊德(Floyd)核心語句
    for(int k=1; k<=n; k++)
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                if(map[i][k]+map[k][j]<map[i][j])
                    map[i][j]=map[i][k]+map[k][j];
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
            printf("%10d",map[i][j]);
        printf("\n");
    }
    return 0;
}

給出樣例：

輸入：

輸出：

         0         2         5         4
         9         0         3         4
         6         8         0         1
         5         7        10         0

輸出的就是我建圖的時(shí)候用的表格，可以表示任意一點(diǎn)到任意一點(diǎn)的最短距離。
如果有什么不對(duì)的地方，歡迎指正~~

到此這篇關(guān)于C++的最短路徑的弗洛伊德算法案例講解的文章就介紹到這了,更多相關(guān)C++的最短路徑的弗洛伊德算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: