Dijkstra(最短距離)

8890 ワード

例:最短パス
図形の幹線に重み付けがない場合は、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++;
		}
	}
}