C++實(shí)現(xiàn)多源最短路徑之Floyd算法示例

更新時(shí)間：2017年08月04日 11:52:44 作者：ices_

這篇文章主要介紹了C++實(shí)現(xiàn)多源最短路徑之Floyd算法,結(jié)合實(shí)例形式分析了多源最短路徑之Floyd算法的原理、實(shí)現(xiàn)方法及核心代碼,需要的朋友可以參考下

本文實(shí)例講述了C++實(shí)現(xiàn)多源最短路徑之Floyd算法。分享給大家供大家參考，具體如下：

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAX 999
using namespace std;
int n,m;
int e[MAX][MAX];
void Init()
{
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
    {
      if(i==j)
        e[i][j]=0;
      else
        e[i][j]=MAX;
    }
}
void Input()
{
  int a,b,c;
  for(int i=1; i<=m; ++i)
  {
    cin>>a>>b>>c;
    e[a][b]=c;
  }
}
void Floyd()
{
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(e[i][j]>e[i][k]+e[k][j])
          e[i][j]=e[i][k]+e[k][j];
}
void Output()
{
  for(int i=1; i<=n; ++i)
    for(int j=1; j<=n; ++j)
      cout<<"dis["<<i<<"]["<<j<<"] = "<<e[i][j]<<endl;
}
int main()
{
  while(1)
  {
    cout<<"n"<<endl;//頂點(diǎn)個(gè)數(shù)
    cin>>n;
    if(!n) break;
    cout<<"m"<<endl;//邊的個(gè)數(shù)
    cin>>m;
    Init();
    Input();
    Floyd();
    Output();
  }
}

Floyd算法是求多點(diǎn)最短路徑的一種算法，其核心代碼為

void Floyd()
{
  for(int k=1; k<=n; k++)
    for(int i=1; i<=n; i++)
      for(int j=1; j<=n; j++)
        if(e[i][j]>e[i][k]+e[k][j])
          e[i][j]=e[i][k]+e[k][j];
}

希望本文所述對(duì)大家C++程序設(shè)計(jì)有所幫助。

您可能感興趣的文章:

C++
算法

相關(guān)文章

C++?shared_ptr智能指針reset()使用示例詳解
這篇文章主要為大家介紹了C++?shared_ptr智能指針reset()使用示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
2023-08-08
C語(yǔ)言超全面講解函數(shù)的使用方法上
函數(shù)是一組一起執(zhí)行一個(gè)任務(wù)的語(yǔ)句。每個(gè)?C?程序都至少有一個(gè)函數(shù)，即主函數(shù)?main()?，所有簡(jiǎn)單的程序都可以定義其他額外的函數(shù)，由于篇幅過大，分為兩篇講解，下面開始上篇
2022-04-04
C語(yǔ)言編程數(shù)據(jù)在內(nèi)存中的存儲(chǔ)詳解
本篇文章是C語(yǔ)言編程篇，主要為大家介紹C語(yǔ)言編程中數(shù)據(jù)在內(nèi)存中存儲(chǔ)解析，有需要的朋友可以借鑒參考下，希望可以有所幫助
2021-09-09
C++修煉之拷貝構(gòu)造函數(shù)
這篇文章主要內(nèi)容是6個(gè)默認(rèn)成員函數(shù)之一的拷貝構(gòu)造函數(shù)的認(rèn)識(shí)與學(xué)習(xí)，讓同學(xué)們充分理解淺拷貝與深拷貝，感興趣的小伙伴可以參考閱讀
2023-04-04
C語(yǔ)言獲取文件大小的兩種方式
因?yàn)橐粢曨l開發(fā)的需要,經(jīng)常會(huì)寫一些文件輸入輸出的測(cè)試程序,常常用到獲取文件大小的函數(shù),本篇文章就記錄一下常用的兩種獲取文件大小的方式,希望對(duì)大家有所幫助
2023-11-11
C語(yǔ)言中pthread_exit()函數(shù)實(shí)現(xiàn)終止線程
本文主要介紹了C語(yǔ)言中pthread_exit()函數(shù)實(shí)現(xiàn)終止線程，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2023-05-05
C++基于EasyX實(shí)現(xiàn)簡(jiǎn)單掃雷游戲
這篇文章主要為大家詳細(xì)介紹了C++基于EasyX實(shí)現(xiàn)簡(jiǎn)單掃雷游戲，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2020-02-02
Cocos2d-x中CCEditBox文本輸入框的使用實(shí)例
這篇文章主要介紹了Cocos2d-x中CCEditBox文本輸入框的使用實(shí)例,本文在代碼中用大量注釋講解了CCEditBox的使用方法,需要的朋友可以參考下
2014-09-09
使用用C++做一顆會(huì)跳動(dòng)的愛心實(shí)例代碼
大家好，本篇文章主要講的是使用用C++做一顆會(huì)跳動(dòng)的愛心實(shí)例代碼，感興趣的同學(xué)趕快來(lái)看一看吧，歡迎借鑒學(xué)習(xí)C++做一顆會(huì)跳動(dòng)的愛心實(shí)例代碼
2021-12-12
C++實(shí)現(xiàn)簡(jiǎn)單學(xué)生成績(jī)管理系統(tǒng)
這篇文章主要為大家詳細(xì)介紹了C++實(shí)現(xiàn)簡(jiǎn)單學(xué)生成績(jī)管理系統(tǒng)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2022-03-03