ジョンソンのアルゴリズムを使った最短経路問題の解法
まず、ジョンソンのアルゴリズムの基本的なアイデアを理解しましょう。このアルゴリズムでは、最短経路問題を単一始点最短経路問題に変換します。具体的には、元のグラフに新たな頂点を追加し、その頂点から他の全ての頂点への距離を0とします。その後、この新たなグラフ上でベルマン-フォードアルゴリズムを実行することで、全ての頂点間の最短経路を求めることができます。>>More
Home > 最短経路問題
Bellman-Fordアルゴリズム:最短経路問題の解決方法
#include <iostream> #include <vector> #include <limits> struct Edge { int source, destination, weight; }; void BellmanFord(std::vector<Edge>& edges, int numVertices, int source) { std::vector<int> distance(numVertices, std::numeric_limits<int>::max());>>More
Floyd-Warshallアルゴリズム:グラフの最短経路問題の解決方法
Floyd-Warshallアルゴリズムの原因と分析: Floyd-Warshallアルゴリズムは、全頂点対間の最短経路を求めることができるアルゴリズムです。そのため、グラフ内の任意の2つの頂点間の最短経路を求めることができます。このアルゴリズムは、動的計画法の一種であり、頂点の中間経路を考慮しながら最短経路を更新していくことで解を求めます。具体的な手順としては、3重のforループを使用して各頂点を中間頂点として考え、最短経路を更新していくというものです。>>More
Floyd-Warshallアルゴリズム:全点対最短経路問題の解決方法
Floyd-Warshallアルゴリズムの原理は比較的単純です。アルゴリズムは、すべての頂点のペアに対して、それらを直接結ぶ辺の距離を初期値として設定します。そして、すべての頂点を経由する経路の距離を順次更新していきます。具体的には、各頂点を中継点として考え、その中継点を経由する経路の距離がより短くなる場合には、距離を更新します。この更新処理を繰り返すことで、最終的にすべての頂点間の最短経路の距離が求められます。>>More