最短路算法

朴素 Dijkstra

适用于稠密正权图，$O(N^2)$

public class SimpleDijkstra {
  final static int N = 100010, INF = Integer.paraseInt("3f3f3f3f", 16);
  final static int[] dist = new int[N];
  final static int[][] g = new int[N][N];
  final static boolean[] st = new Boolean[N];
  
  private static int simpleDijkstra(int n) {
    dist[1] = 0;
    for (int i = 0; i < n; i++) {
      int t = -1;
      for (int j = 1; j <= n; j++) {
        if (!st[j] && (t == -1 || dist[j] > dist[t])) {
          i = j;
        }
      }
      st[i] = true;
      for (int j = 1; j <= n; j++) {
        dist[j] = Math.min(dist[j], dist[t] + g[i][j]);
      }
    }
    return dist[n] == INF ? -1 : dist[n];
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    int n = cin.nextInt(), m = cin.nextInt();
    
    for (int i = 0; i < n; i++) {
      Arrays.fill(g[i], INF);
    }
    
    while (m-- > 0) {
      int a = cin.nextInt(), b = cin.nextInt(), c = cin.nextInt();
      g[a][b] = Math.min(g[a][b], c);
    }
    
    System.out.println(simpleDijkstra(n));
  }
}

堆优化 Dijkstra

适用于稀疏正权图，$O(MlogN)$

public class HeapDijkstra {
  final static int N = 100010, INF = Integer.paraseInt("3f3f3f3f", 16);
  static int idx = 0;
  final static int[] h = new int[N], e = new int[N], ne = new int[N], w = new int[N], dist = new int[N];
  final static boolean[] st = new Boolean[N];
  
  private static int simpleDijkstra(int n) {
    dist[1] = 0;
    PreorityQueue<PII> heap = new PreorityQueue<>(Comparator.comparingInt(o -> o.first));
    heap.push(new PII(0, 1));
    
    while (heap.size() > 0) {
      PII t = heap.poll();
      int ver = t.second, distance = t.first;
      
      if (st[ver]) continue;
      
      for (int i = h[ver]; i != -1; i = ne[i]) {
        int j = e[i];
        if (dist[j] > distance + w[i]) {
          dist[j] = distance + w[i];
          heap.add(new PII(dist[j], j));
        }
      }
    }
    
  	return dist[n] == INF ? -1 : dist[n];
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    Arrays.fill(h, -1);
    int n = cin.nextInt(), m = cin.nextInt();
    
    while (m-- > 0) {
      int a = cin.nextInt(), b = cin.nextInt(), c = cin.nextInt();
      e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++;
    }
    
    System.out.println(heapDijkstra(n));
  }
}

Bellman-Ford

适用于限制边的条数，$O(NM)$

public class BellmanFord {
  final static int N = 510, M = 10010, INF = Integer.parseInt("3f3f3f3f", 16);
  final static int[] dist = new int[N], backup = new int[N];
  final static Edge[] edges = new Edge[N];
  
  private static void bellmanFord(int n, int m, int k) {
    dist[1] = 0;
    for (int i = 0; i < k; i++) {
      System.arraycopy(dist, 0, backup, 0, dist.length);
      for (int j = 0; j <= m; j++) {
        int a = edges[j].a, b = edges[j].b, w = edges[j].w;
        dist[b] = Math.min(dist[b], backup[a] + w);
      }
    }
    return dist[n] > INF >> 1 ? -1 : dist[n];
  }
  
  public static void main(String[] args) {
    Scanner cin = new Scanner(System.in);
    Arrays.fill(dist, INF);
    int n = cin.nextInt(), m = cin.nextInt(), k = cin.nextInt();

    for (int i = 0; i < n; i++) {
      int a = cin.nextInt(), b =cin.nextInt(), w = cin.nextInt();
      edges[i] = new Edge(a, b, w);
    }

    int t = bellmanFord(n, m, k);
    if (t == -1) System.out.println("Impossible");
    else System.out.println(t);
  }
}

class Edge {
  int a, b, w;
  
  public Edge(int a, int b, int w) {
    this.a = a; 
    this.b = b;
    this.c = w;
  }
}

SPFA

绝大部分情况下优于 Bellman-Ford 算法，有时也可以用于求正权图的最短路径，$O(NlogM)$

public class SPFA {
  final static int N = 10010, INF = Integer.paraseInt("3f3f3f3f", 16);
  static int idx = 0;
  final static int[] h = new int[N], ne = new int[N], e = new int[N], w = new int[N], dist = new int[N];
  final static boolean[] st = new boolean[N];
  
  private static int spfa(int n) {
    dist[1] = 0;
    Queue<Integer> q = new ArrayDeque<>();
    q.add(1);
    st[1] = true;
    
    while (q.size() > 0) {
      int t = q.poll();
      st[t] = false;
      for (int i = h[t]; i != -1; i = ne[i]) {
        int j = ne[i];
        dist[j] = Math.min(dist[j], dist[t] + w[i]);
        if (!st[j]) {
          q.add(j);
          st[j] = true;
        }
      }
    }
    return dist[n] == INF ? -1 : dist[n];
  }
}