「shortest path」の編集履歴（バックアップ）一覧はこちら

「shortest path」(2013/10/08 (火) 12:54:29) の最新版変更点

追加された行は緑色になります。

削除された行は赤色になります。

-Bellman-Ford法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

void bellman_ford(int s) {
	int n = cost.length;
	d = new int[n];
	for (int i = 0; i < d.length; i++)
		d[i] = INF;
	d[s] = 0;
	boolean update;
	while (true) {
		update = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (cost[i][j] != INF) {
					if (d[i] != INF && d[i] + cost[i][j] < d[j]) {
						d[j] = d[i] + cost[i][j];
						update = true;
					}
				}
			}
		}
		if (!update) break;
	}
}
}}

-Dijkstra法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

void dijkstra(int s) {
	int n = cost.length;
	d = new int[n];
	boolean[] used = new boolean[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		
		if (v == -1) break;
		used[v] = true;
		
		for (int u = 0; u < n; u++) {
			d[u] = Math.min(d[u], d[v]+cost[v][u]);
		}
	}
}
}}

-Warshall-Floyd法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[][] d;

void warshall_floyd() {
	int n = cost.length;
	d = new int[n][n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			d[i][j] = cost[i][j];
	for (int i = 0; i < n; i++)
		d[i][i] = 0;
	
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				d[i][j] = Math.min(d[i][j], d[i][k]+d[k][j]);
}
}}

-辺クラス
#highlight(java){{
class Edge {
	int to;
	int cost;
	Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}
}
}}

-Bellman-Ford法(隣接リスト)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;
int[] d;

void bellman_ford(int s) {
	int n = list.length;
	d = new int[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	boolean update;
	while (true) {
		update = false;
		for (int i = 0; i < n; i++) {
			for (Edge e : list[i]) {
				if (d[i] != INF && d[i] + e.cost < d[e.to]) {
					d[e.to] = d[i] + e.cost;
					update = true;
				}
			}
		}
		if (!update) break;
	}
}
}}

-Dijkstra法(隣接リスト)
#highlight(java){{
class Pair implements Comparable<Pair> {
	int index;
	int distance;
	Pair(int i, int d) {
		index = i;
		distance = d;
	}
	@Override
	public int compareTo(Pair o) {
		return distance - o.distance;
	}
	
}

final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;
int[] d;

void dijkstra(int s) {
	int n = list.length;
	d = new int[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	Queue<Pair> queue = new PriorityQueue<Pair>();
	queue.add(new Pair(s, 0));
	
	while (!queue.isEmpty()) {
		Pair p = queue.poll();
		int v = p.index, dis = p.distance;
		if (d[v] < dis) continue;
		for (Edge e : list[v]) {
			if (d[v] + e.cost < d[e.to]) {
				d[e.to] = d[v] + e.cost;
				queue.add(new Pair(e.to, d[e.to]));
			}
		}
	}
}
}}

-負の閉路がある場合はtrueを返す(隣接リスト)
#highlight(java){{
List<Edge>[] list;
int[] d;

boolean find_negative_loop() {
	int n = list.length;
	d = new int[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (Edge e : list[j]) {
				if (d[j] + e.cost < d[e.to]) {
					d[e.to] = d[j] + e.cost;
					
					if (i == n-1) return true;
				}
			}
		}
	}
	return false;
}
}}

-負の閉路がある場合はtrueを返す(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

boolean find_negative_loop() {
	int n = cost.length;
	d = new int[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (cost[j][k] != INF) {
					if (d[j] + cost[j][k] < d[k]) {
						d[k] = d[j] + cost[j][k];
						
						if (i == n-1) return true;
					}
				}
			}
		}
	}
	return false;
}
}}

-Bellman-Ford法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

void bellman_ford(int s) {
	int n = cost.length;
	d = new int[n];
	for (int i = 0; i < d.length; i++)
		d[i] = INF;
	d[s] = 0;
	boolean update;
	while (true) {
		update = false;
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (cost[i][j] != INF) {
					if (d[i] != INF && d[i] + cost[i][j] < d[j]) {
						d[j] = d[i] + cost[i][j];
						update = true;
					}
				}
			}
		}
		if (!update) break;
	}
}
}}

-Dijkstra法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

void dijkstra(int s) {
	int n = cost.length;
	d = new int[n];
	boolean[] used = new boolean[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		
		if (v == -1) break;
		used[v] = true;
		
		for (int u = 0; u < n; u++) {
			d[u] = Math.min(d[u], d[v]+cost[v][u]);
		}
	}
}
}}

-Warshall-Floyd法(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[][] d;

void warshall_floyd() {
	int n = cost.length;
	d = new int[n][n];
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			d[i][j] = cost[i][j];
	for (int i = 0; i < n; i++)
		d[i][i] = 0;
	
	for (int k = 0; k < n; k++)
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				d[i][j] = Math.min(d[i][j], d[i][k]+d[k][j]);
}
}}

-辺クラス
#highlight(java){{
class Edge {
	int to;
	int cost;
	Edge(int to, int cost) {
		this.to = to;
		this.cost = cost;
	}
}
}}

-Bellman-Ford法(隣接リスト)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;
int[] d;

void bellman_ford(int s) {
	int n = list.length;
	d = new int[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	boolean update;
	while (true) {
		update = false;
		for (int i = 0; i < n; i++) {
			for (Edge e : list[i]) {
				if (d[i] != INF && d[i] + e.cost < d[e.to]) {
					d[e.to] = d[i] + e.cost;
					update = true;
				}
			}
		}
		if (!update) break;
	}
}
}}

-Dijkstra法(隣接リスト)
#highlight(java){{
class Pair implements Comparable<Pair> {
	int index;
	int distance;
	Pair(int i, int d) {
		index = i;
		distance = d;
	}
	@Override
	public int compareTo(Pair o) {
		return distance - o.distance;
	}
	
}

final int INF = Integer.MAX_VALUE/2;
List<Edge>[] list;
int[] d;

void dijkstra(int s) {
	int n = list.length;
	d = new int[n];
	Arrays.fill(d, INF);
	d[s] = 0;
	Queue<Pair> queue = new PriorityQueue<Pair>();
	queue.add(new Pair(s, 0));
	
	while (!queue.isEmpty()) {
		Pair p = queue.poll();
		int v = p.index, dis = p.distance;
		if (d[v] < dis) continue;
		for (Edge e : list[v]) {
			if (d[v] + e.cost < d[e.to]) {
				d[e.to] = d[v] + e.cost;
				queue.add(new Pair(e.to, d[e.to]));
			}
		}
	}
}
}}

-負の閉路がある場合はtrueを返す(隣接リスト)
#highlight(java){{
List<Edge>[] list;
int[] d;

boolean find_negative_loop() {
	int n = list.length;
	d = new int[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (Edge e : list[j]) {
				if (d[j] + e.cost < d[e.to]) {
					d[e.to] = d[j] + e.cost;
					
					if (i == n-1) return true;
				}
			}
		}
	}
	return false;
}
}}

-負の閉路がある場合はtrueを返す(隣接行列)
#highlight(java){{
final int INF = Integer.MAX_VALUE/2;
int[][] cost;
int[] d;

boolean find_negative_loop() {
	int n = cost.length;
	d = new int[n];
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			for (int k = 0; k < n; k++) {
				if (cost[j][k] != INF) {
					if (d[j] + cost[j][k] < d[k]) {
						d[k] = d[j] + cost[j][k];
						
						if (i == n-1) return true;
					}
				}
			}
		}
	}
	return false;
}
}}

-経路復元(Dijkstra)
#highlight(java){{
int[][] cost;
int[] d;
int[] prev;

void dijkstra(int s) {
	int n = cost.length;
	d = new int[n];
	prev = new int[n];
	boolean[] used = new boolean[n];
	Arrays.fill(d, INF);
	Arrays.fill(prev, -1);
	d[s] = 0;
	
	while (true) {
		int v = -1;
		for (int u = 0; u < n; u++) {
			if (!used[u] && (v == -1 || d[u] < d[v])) v = u;
		}
		
		if (v == -1) break;
		used[v] = true;
		
		for (int u = 0; u < n; u++) {
			d[u] = Math.min(d[u], d[v]+cost[v][u]);
			prev[u] = v;
		}
	}
}
}}