単一始点最短路(Single-Source Shortest Path)

リポジトリ
グラフの基本要素はグラフ(Graph) - kanetaiの二次記憶装置のほうにまとめる。
計算結果の単一始点最短距離とバックポインタ。buildPathで最短経路を構築する。

/** Results of Single-Source Shortest Path (SSSP) Algorithm */
public static class SSSPResult{
	private int[] dist; // dist[d]:= shortest path to d
	private int[] prev; // back pointers
	private boolean hasNegativeCycle;
	public SSSPResult(int[] dist, int[] prev, boolean hasNegativeCycle){ set(dist, prev, hasNegativeCycle); }
	final private void set(int[] dist, int[] prev, boolean hasNegativeCycle){ this.dist = dist; this.prev = prev; this.hasNegativeCycle = hasNegativeCycle; }
	final public int getDist(int i){ return dist[i]; }
	final public int getPrev(int i){ return prev[i]; }
	final public boolean hasNegativeCycle(){ return hasNegativeCycle; }
	/**
	 * Builds the shortest path from results of Single-Source Shortest Path (SSSP) Algorithm<br>
	 * @param results	results of SSSP Algorithm
	 * @param d		destination node
	 * @return		the shortest path to d
	 */
	public List<Integer> buildPath(int d){
		LinkedList<Integer> path = new LinkedList<Integer>();
		if(dist[d] < INF) for(int u = d; u >= 0; u = prev[u]) path.addFirst(u);
		return path;
	}
}

Dijkstra法(Dijkstra's algorithm)

負辺がないグラフの単一始点最短路を求めるアルゴリズム
$s$ :始点
$dist(i)$ : ノード $i$ の最短の累積距離
$V$ : 頂点集合
$U$ : 最短距離確定頂点(未到達)集合
$weight(i,j)$ : ノード $i$ からノード $j$ への辺のコスト(距離, 重み)

$\forall i:dist(i)=\infty, U=V$ で初期化
$dist(s) \leftarrow 0$

$U = \phi$ になるまで以下を繰り返す。

$v = {\arg\min}_{u\in U}dist(u)$ 　// $v$ への最短距離確定
$U \leftarrow U \cup \{v\}$

$v$ の隣接ノード $u$ の $dist$ を更新する。
(この時点で $x\in V-U$ は最短距離確定なので必ず $u\in U$ )

$dist(u) \leftarrow dist(v) + weight(v, u)$

これで最短距離が求まる。

Dijkstra （密グラフ向け）

隣接行列でやるやり方。 $O(|V|^2)$
$v$ を選んだときバックポインタを覚えて、buildPath()で最短路を構築すればよいが、
頂点を持っているだけだと $v$ がどの頂点から来たかがわからないので、 $dist(u)$ の更新時に記憶する。

/**
 * Gets single-source shortest distances and back pointers for building a shortest path 
 * via Dijkstra's algorithm(naive O(|V|^2)).<br>
 * @param G	adjacency matrix(|V|×|V|) (※edge weights must be positive)
 * @param s	source node
 * @return	SSSPResult
 */
public static SSSPResult Dijkstra(int[][] G, int s){
	int n = G.length;
	int[] dist = new int[n]; Arrays.fill(dist, INF);
	int[] prev = new int[n]; Arrays.fill(prev, -1);
	boolean[] visited = new boolean[n]; Arrays.fill(visited, false);

	dist[s] = 0;
	while(true){
		int v = -1;
		for(int u = 0; u < n; ++u)
			if(!visited[u] && (v == -1 || dist[u] < dist[v])) v = u;
		if(v < 0) break;
		visited[v] = true;

		for(int u = 0; u < n; ++u){
			int newDist = dist[v] + G[v][u];
			if(dist[u] > newDist){
				dist[u] = newDist;
				prev[u] = v;
			}
		}
	}
	return new SSSPResult(dist, prev, false);
}

Dijkstra （疎グラフ向け）

$U$ にヒープを使えば、
初期化は $O(|V| + |V|\log |V|)=O(|V|\log |V|)$ 。
$v = {\arg\min}_{u\in U}dist(u)$ 　 $U \leftarrow U \cup \{v\}$ は $|V|$ 回
$dist(u) \leftarrow dist(v) + weight(v, u)$ で距離更新(DecreaseKey(u, dist(u)))は $|E|$ 回
行われる。
$0 < |U| \leq |V|$ なので、全体の計算量は $O((|E|+|V|)\log |V|)$ 。
密だと $O(|E|)\rightarrow O(|V|^2)$ となるので、全体の計算量は $O(|V|^2\log |V|)$ になってしまう。

priority queueがDecreaseKeyをサポートしていない場合は、下のような実装でだいたい $O(|E|\log |V|)$ にできる。
priority queueに $|E|$ 個要素が追加される事になるが、最小値を取り出したときに、最短距離が確定していたらスキップすることにより、全体の計算量は $O(|E|\log |V|)$ になる。(プログラミングコンテストチャレンジブック [第2版]　?問題解決のアルゴリズム活用力とコーディングテクニックを鍛える?p97)
バックポインタprevは最短距離確定時に記憶しているので、（密グラフ向け）でのvisitedの代わりに使える。

/**
 * Gets single-source shortest distances and back pointers for building a shortest path 
 * via Dijkstra's algorithm O(|E|log|V|).<br>
 * @param list	adjacency list (※edge weights must be positive)
 * @param s	source node
 * @return	SSSPResult
 */
public static SSSPResult Dijkstra(List<List<Edge>> list, int s){
	int n = list.size();
	int[] dist = new int[n]; Arrays.fill(dist, INF);
	int[] prev = new int[n]; Arrays.fill(prev, -1);
	PriorityQueue<Edge> q = new PriorityQueue<Edge>(n*n);

	dist[s] = 0;
	q.add(new Edge(-1, s, 0));
	while(!q.isEmpty()){
		Edge p = q.poll();
		int v = p.d;
		if(prev[v] != -1) continue; //dist[v] < p.weight
		prev[v] = p.s;
		for(final Edge u: list.get(v)){ //※u.s = v
			int newDist = dist[v] + u.w;
			if(dist[u.d] > newDist){
				dist[u.d] = newDist;
				q.add(new Edge(u.s, u.d, dist[u.d]));
			}
		}
	}
	return new SSSPResult(dist, prev, false);
}

Bellman-Ford法(Bellman-Ford algorithm)

グラフの単一始点最短路を求めるアルゴリズム。Dijkstra法とは異なり負辺を含んでいても良い。
$dist(s)=0$ 　 $s:$ 始点
で初期化しておく。
$dist(i)=\min\{dist(j) + weight(j,i) | (j,i)\in E\}$ で更新( $O(|E|)$
この更新は $|V|-1$ 回行えば単一始点最短距離が求まる。従って全体の計算量は $O(|V||E|)$
アルゴリズムは非常にシンプル。
もし、 $|V|$ 回目で更新が発生したらそれは、負閉路(negative cycle)があるということになる。
密グラフの場合は、計算量が $O(|V|^3)$ になるので、Floyd-Warshall法 $O(|V|^3)$ で全点対間最短路を求めた方が得かもしれない。

/**
 * Gets single-source shortest distance and back pointers for building a shortest path 
 * via Bellman-Ford algorithm O(|V||E|).<br>
 * @param list	adjacency list (※edge weights can be negative)
 * @param s	source node
 * @return	SSSPResult
 */
public static SSSPResult BellmanFord(List<List<Edge>> list, int s) {
	int n = list.size();
	int[] dist = new int[n]; Arrays.fill(dist, INF);
	int[] prev = new int[n]; Arrays.fill(prev, -1);
	boolean hasNegativeCycle = false, updated = true;
	dist[s] = 0;

	for(int k = 1; k <= n && updated; ++k){
		hasNegativeCycle = (k==n);
		updated = false;
		for(int i = 0; i < n; ++i){
			for(final Edge e: list.get(i)){
				int newDist = dist[e.s] + e.w;
				if(dist[e.d] > newDist){
					dist[e.d] = (hasNegativeCycle ? -INF : newDist);
					prev[e.d] = e.s;
					updated = true;
				}
			}
		}
	}
	return new SSSPResult(dist, prev, hasNegativeCycle);
}