読者です 読者をやめる 読者になる 読者になる

kanetaiの二次記憶装置

プログラミングに関するやってみた、調べた系のものをQitaに移して、それ以外をはてブでやる運用にしようと思います。http://qiita.com/kanetai

単一始点最短路(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);
}