shortest path - procom @ ウィキ

• Bellman-Ford法(隣接行列)

  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法(隣接行列)

  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法(隣接行列)

  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]);
  }

• 辺クラス

  class Edge {
  	int to;
  	int cost;
  	Edge(int to, int cost) {
  		this.to = to;
  		this.cost = cost;
  	}
  }

• Bellman-Ford法(隣接リスト)

  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法(隣接リスト)

  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を返す(隣接リスト)

  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を返す(隣接行列)

  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)

  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;
  		}
  	}
  }