C LANGUAGE TECHNOLOGY

【C言語】最短経路問題を解くアルゴリズム【ダイクストラ法,ワーシャル・フロイド法】

悩んでいる人

C言語で最短経路問題を解くアルゴリズムを教えて!

こういった悩みにお答えします.

本記事の信頼性

  • リアルタイムシステムの研究歴12年.
  • 東大教員の時に,英語でOSの授業.
  • 2012年9月~2013年8月にアメリカのノースカロライナ大学チャペルヒル校コンピュータサイエンス学部2021年の世界大学学術ランキングで20位)で客員研究員として勤務.C言語でリアルタイムLinuxの研究開発
  • プログラミング歴15年以上,習得している言語: C/C++Solidity/Vyper,Java,Python,Ruby,HTML/CSS/JS/PHP,MATLAB,Assembler (x64,ARM).
  • 東大教員の時に,C++言語で開発した「LLVMコンパイラの拡張」,C言語で開発した独自のリアルタイムOS「Mcube Kernel」GitHubにオープンソースとして公開

こういった私から学べます.

最短経路問題

最短経路問題とは,グラフ理論において重み付きグラフの与えられた2つのノード間を結ぶ経路の中で,重みが最小の経路を求める最適化問題です.

最短経路問題は,主に単一始点最短経路問題(SSSP:Single Source Shortest Path)と全ペア対最短経路問題(APSP : All Pair Shortest Path)の2種類があります.

本記事では,単一始点最短経路問題の代表的なアルゴリズムであるダイクストラ法と,全ペア対最短経路問題の代表的でアルゴリズムであるワーシャル・フロイド法を紹介します.

最短経路問題:ダイクストラ法

ダイクストラ法は,1959年にエドガー・ダイクストラにより提案されたグラフ理論における辺の重みが非負数の場合の単一始点最短経路問題を解くための最良優先探索によるアルゴリズムです.

ダイクストラ法は,最短経路問題を解く代表的なアルゴリズムで,Open Shortest Path First(OSPF)等のインターネットルーティングプロトコルや,カーナビの経路探索や鉄道の経路案内に利用されています.

ダイクストラ法の解説は,こちらの動画がわかりやすいです.

ダイクストラ法のコードは以下になります.

実行結果は以下になります.

全ペア最短経路問題:ワーシャル・フロイド法

ワーシャル・フロイド法は,スティーブン・ワーシャルとロバート・フロイドが独立に提案した重み付き有向グラフの全ペア最短経路問題を多項式時間で解くアルゴリズムです.

ダイクストラ法は単一始点最短経路問題を解く代表的なアルゴリズムなのに対して,ワーシャル・フロイド法は全ペアの最短経路問題を解く代表的なアルゴリズムになります.

ワーシャル・フロイド法の解説は,こちらの動画がわかりやすいです.

ワーシャル・フロイド法のコードは以下になります.

実行結果は以下になります.

まとめ

C言語で最短経路問題を解くアルゴリズムを紹介しました.

具体的には,ダイクストラ法,ワーシャル・フロイド法を解説しました.

どちらも代表的なアルゴリズムなのできちんと理解しておきましょう!

C言語を独学で習得することは難しいです.

私にC言語の無料相談をしたいあなたは,公式LINE「ChishiroのC言語」の友だち追加をお願い致します.

私のキャパシティもあり,一定数に達したら終了しますので,今すぐ追加しましょう!

友だち追加

独学が難しいあなたは,元東大教員がおすすめするC言語を学べるオンラインプログラミングスクール5社で自分に合うスクールを見つけましょう.後悔はさせません!

-C LANGUAGE, TECHNOLOGY
-, , , , ,