Dijkstra(最短距離)
例:最短パス
図形の幹線に重み付けがない場合は、DFSまたはBFSを使用して最短距離を求めることができます.
しかし,幹線に重みが存在すると,単純なDFSやBFSでは解くことが困難である.
Dijkstraアルゴリズムは,重みのあるグラフィックの1つのノードから他のすべてのノードへの最小コストを求めるアルゴリズムである.
これはgifでマルチコンビネーション動作方式を示す例である.△上の動作は改良された複数の動作です.
まず幹線の情報を隣接リストに保存します.
0番ノードから1番ノード方向に重み8の幹線が存在する場合
重みが増すだけで、既存のBFSやDFSが隣接リストを作成する方法とはあまり変わりません.
重み付けされていない図形を探索する場合,ノード数のみを用いて最短距離を求めると,重み付け和の間で比較する必要がある.
このためには、図形の最短距離を求めるために注釈を使用する配列であるdistという配列を別途作成し、適切な値に初期化する必要がある.
まず,自身までの距離が0であるため,複数のアルゴリズムを用いる前にdist配列を以下に示す.
優先順位キューに自分の距離と自分のノード番号を追加します.
次に、優先度キューから最も優先度の高いpairを取り出し、ノードの隣接リストに含まれるすべての幹線をチェックし、コストが更新されると、隣接リストから幹線情報を抽出し、優先度キューに入れます.
以上を繰り返し、重み付け値を更新します.
上記の手順が終了すると、0番ノードから残りのすべてのノードまでの距離はこのように保存されます.
優先キューを使用するマルチタスクは、常に最短距離を保証します.
ただし、負の周期がある場合は、多出力アルゴリズムを適用することはできない.
例:タイムマシン
この例は、マルチアウトプットアルゴリズムではなく、ベルマン・フォードアルゴリズムを使用するべきである.
図形の幹線に重み付けがない場合は、DFSまたはBFSを使用して最短距離を求めることができます.
しかし,幹線に重みが存在すると,単純なDFSやBFSでは解くことが困難である.
Dijkstraアルゴリズムは,重みのあるグラフィックの1つのノードから他のすべてのノードへの最小コストを求めるアルゴリズムである.
さぎょうモード
これはgifでマルチコンビネーション動作方式を示す例である.△上の動作は改良された複数の動作です.
隣接リストを使用して幹線を保存
まず幹線の情報を隣接リストに保存します.
ベクトル宣言
#include <vector>
using namespace std;
vector<pair<int, int> > v[N];
このようにベクトルを構成すれば,N個のノードに対してそれぞれ幹線情報を格納することができる.0番ノードから1番ノード方向に重み8の幹線が存在する場合
v[0].push_back(1, 8);
と同様に格納される.重みが増すだけで、既存のBFSやDFSが隣接リストを作成する方法とはあまり変わりません.
ディスクアレイの初期化
重み付けされていない図形を探索する場合,ノード数のみを用いて最短距離を求めると,重み付け和の間で比較する必要がある.
このためには、図形の最短距離を求めるために注釈を使用する配列であるdistという配列を別途作成し、適切な値に初期化する必要がある.
#define INF 1000000000
int dist[N];
void init_dist()
{
int i;
i = 0;
while (i++ < N)
dist[i] = INF;
}
dist配列は最大値に更新され続けるため、十分な値で初期化する必要があります.dijkstraアルゴリズムの実装
void Dijkstra(int start)
{
int cost, cur;
int ncost, next;
int i;
priority_queue<pair<int, int> > pq;
dist[start] = 0;
pq.push(make_pair(0, start));
while (!pq.empty())
{
cost = -pq.top().first;
cur = pq.top().second;
pq.pop();
i = 0;
while (i < v[cur].size())
{
next = v[cur][i].first;
ncost = v[cur][i].second;
if (dist[next] > cost + ncost)
{
dist[next] = cost + ncost;
pq.push(make_pair(-dist[next], next));
}
i++;
}
}
}
以上の図とコードを用いて多出力アルゴリズムを把握する.まず,自身までの距離が0であるため,複数のアルゴリズムを用いる前にdist配列を以下に示す.
優先順位キューに自分の距離と自分のノード番号を追加します.
次に、優先度キューから最も優先度の高いpairを取り出し、ノードの隣接リストに含まれるすべての幹線をチェックし、コストが更新されると、隣接リストから幹線情報を抽出し、優先度キューに入れます.
以上を繰り返し、重み付け値を更新します.
上記の手順が終了すると、0番ノードから残りのすべてのノードまでの距離はこのように保存されます.
優先キューを使用するマルチタスクは、常に最短距離を保証します.
ただし、負の周期がある場合は、多出力アルゴリズムを適用することはできない.
例:タイムマシン
この例は、マルチアウトプットアルゴリズムではなく、ベルマン・フォードアルゴリズムを使用するべきである.
Reference
この問題について(Dijkstra(最短距離)), 我々は、より多くの情報をここで見つけました https://velog.io/@woonchoi/Dijkstra-다익스트라-최단거리テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol