没有楼的楼长的博客

ダイクストラ#

ダイクストラは、単一始点最短経路アルゴリズムで、貪欲法と幅優先探索を利用しています。時間計算量は SPFA の時間計算量よりもわずかに低く、負の辺の重みがなく、ランダムデータでない場合（SPFA が効かない場合）に適しています。

ダイクストラは貪欲な戦略を用いて、各点と始点の距離を dis 配列に保存します。この点が始点と直接接続されていない場合、その距離は無限大（ここでは$0x7fffffff$（int の最大値）で代用）と見なします。すでに処理された（最短経路であることが確定した）頂点は配列にマークされます。

では、どう処理するのでしょうか？

まず、始点と直接接続されている点を一通り巡回し、始点からの距離が最小の点を見つけます。ここではそれを A 点と呼び、処理済みとしてマークします。なぜこれで A 点が処理済みになるのでしょうか？それは、貪欲法の考え方に従い、A 点が始点からの距離が最小であれば、始点から他の点を経由して A 点に行く距離は、始点から A 点に直接行く距離よりも大きくなるからです（これがダイクストラが負の辺の重みを持つグラフに適用できない理由でもあります）。次に、A 点に接続されているすべての点を巡回し、始点から A 点を経由してこの点に行く距離が、始点からこの点に直接行く距離よりも小さい場合、始点からこの点への距離を更新します。この操作を「緩和」と呼びます。これをすべての頂点が緩和されるまで繰り返します。

上図開講#

まず、次のようなグラフを構築します。

A を始点とし、dis 配列は次のようになります（インデックスは 0 から始まります）。

dis 配列を一通り巡回し、A から最も近い点 E を見つけ、処理済みの点としてマークします（緑色）。

次に、E に接続されている点を巡回し、始点から E 点を経由してこの点に行く距離が、始点からこの点に直接行く距離よりも短い場合、始点からこの点への距離を更新します。例えば B 点の場合、始点から E 点を経由して B 点に行く距離（15）は、始点から B 点に直接行く距離（$\infty$）よりも小さいため、dis 配列の B 点への距離を更新します。（赤色は処理済みだが不確定な点を示し、プログラム内ではマークされず、説明のために便利です）

次に F 点を巡回すると、A-B-F の距離（9）が A-F の距離（10）よりも小さいことがわかり、dis 配列の A-F の距離を更新します。

E 点に接続されている点をすべて巡回した後、再度 dis 配列を巡回し、処理されていない A から最も近い点を見つけ、E 点のステップを繰り返します。すべての点が処理されるまで続けます。

F 点を確定した点としてマークします。

F 点に接続されている点を巡回し、距離を更新します。F 点に接続されている点はなく、dis 配列を巡回して次の点を探します。

B 点を確定した点としてマークします。

B 点に接続されている点を巡回し、距離を更新します。B 点に接続されている点はなく、dis 配列を巡回して次の点を探します。

C を確定した点としてマークします。

C 点に接続されている点を巡回し、距離を更新します。

D 点を見つけ、$20+5<\infty$であるため、A 点から D 点への距離を 25 に更新します。

C 点に接続されている点はなくなり、dis 配列を巡回して次の点を探します。

D を確定した点としてマークします。

すべての点が更新され、A 点からすべての点への最短経路の長さが得られました。

これがダイクストラを利用して単一始点最短経路を見つける方法です。

なぜ負の辺の重みを持つグラフに使えないのか#

なぜダイクストラが負の辺の重みを持つグラフに使えないのでしょうか？それを説明するために、次のグラフを見てみましょう。

A 点を始点とし、最初の dis 配列は次のようになります。

ダイクストラの手順に従うと、最初のステップで C 点が確定されます。

しかし、5 は A 点から C 点への最短距離ではなく、A-B-C の距離は 0 であり、明らかに 5 よりも小さいですが、すでに A-C の距離が確定されているため、更新は行われず、誤った答えが出力されてしまいます。

ダイクストラは本当に難しいアルゴリズムです

最後に、皆さんが最も欲しいものです。

テンプレート#

隣接行列の保存（始点は 1）：

void dijkstra()
{
    memset(dis,127/3,sizeof(dis));//初期化
    v[1]=1;
    dis[1]=0;
    for(int i=1;i<=n;++i)
    {
        int k=0;
        for(int j=1;j<=n;++j)//最も近い点を見つける
            if(!v[j]&&(k==0||dis[j]<dis[k]))
                k=j;
        v[k]=1;//集合に追加
        for(int j=1;j<=n;++j)//緩和
            if(!v[j]&&dis[k]+a[k][j]<dis[j])
                dis[j]=dis[k]+a[k][j];
    }
}

隣接リストの保存（ヒープ最適化付き）：

using namespace std;
const int maxn=250;
struct edge{
	int to,dis,next;
	//辺の構造体を定義
};
edge e[maxn*2]; //辺のリスト
int head[maxn],dis[maxn],cnt;
bool vis[maxn];
int n,a,b;

inline void add_edge(int u,int v,int d){
	cnt++;//辺を追加
	e[cnt].dis=d;
	e[cnt].to=v;
	e[cnt].next=head[u];
	head[u]=cnt;//前の辺を保存
}

struct node{
	int dis;//点の構造体、disはA点からこの点までの距離
	int pos;
	bool operator <(const node &x)const
	{
		return x.dis<dis;//演算子をオーバーロード、さもなければc++では比較できない
	}
};

priority_queue<node> q;

inline void dij(){
	dis[a]=0;
	q.push((node){0,a});
	while(!q.empty()){
		node tmp=q.top();
		q.pop();
		int x=tmp.pos,d=tmp.dis;
		if(vis[x]) continue;
		vis[x]=1;
		for(int i=head[x];i;i=e[i].next){
			int y=e[i].to;
			if(dis[y]>dis[x]+e[i].dis){
				dis[y]=dis[x]+e[i].dis; //緩和
				if(!vis[y]){
					q.push((node){dis[y],y});//キューに追加
				}
			}
		}
	}
}

私のコードは本当に醜い