shortest path


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

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