こんにちは!ganariyaです。 今回はグラフ理論のアルゴリズム、「ワーシャルフロイド」についてです。 実世界において、グラフ理論はあらゆるところで利用されます。 例えば、インターネットにおける通信パスや、JRなどの電車の経路パス探索です。 これらはグラフ理論を発展させて、実務的に使用しているものです。 グラフ理論は殆ど、駅などをノード、道路などをエッジとして扱い、点と線が結ばれたものとして扱われます。 グラフのキホン(1)グラフ概要編やグラフのキホン(2)表現方法と探索編の記事を読むとグラフの基礎が身につくと思います。 そして、グラフ理論で扱われる大きなジャンルの一つには、最短経路問題というものがあります。 これは、与えられたグラフの2つのノード間の最小のコストの経路を見つけるというものです。 例えば、以下のようなグラフがあったとします。 グラフ 以上のようなグラフで、始点から終点まで
![ワーシャルフロイド 入門 - TechFULの中の人](https://cdn-ak-scissors.b.st-hatena.com/image/square/ef592adace40862d337901ba6c1f85fb8c25e600/height=288;version=1;width=512/https%3A%2F%2Fcdn-ak.f.st-hatena.com%2Fimages%2Ffotolife%2Fg%2Fganariya%2F20190216%2F20190216103745.png)