Shortest Paths

Dijkstra, Bellman-Ford, SPFA

Dijkstra

class Example {
  Map<Integer, List<int[]>> G; // G is a mapping of sourceVertex: [targetVertex, weight]

  void dijkstra(int source, int target) {
    // PQ with [targetVertex, weight]. Sorted by weights in non-decreasing order
    PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
    minHeap.add(new int[] {source, 0});
    int[] minDist = new int[G.size()];
    Arrays.fill(minDist, Integer.MAX_VALUE); // Fill with maxiumum value
    minDist[source] = 0;

    while (minHeap.isEmpty()) {
      int cur = minHeap.remove()[0];
      if (!G.containsKey(cur)) continue; // No edges
      for (int[] nextEdge : G.get(cur)) {
        int nextVertex = nextEdge[0], nextWeight = nextEdge[1];
        if (minDist[nextVertex] > minDist[cur] + nextWeight) {
          minDist[nextVertex] = minDist[cur] + nextWeight;
          minHeap.add(new int[] {nextVertex, minDist[nextVertex]});
        }
      }
    }
  }
}

• Time: O(ElogV)

• Space: O(V)

• Works only with non-negative weights.

Bellman-Ford

class Example {
  List<int[]> edges; // edges is a list of: [source, target, weight]

  int bellmanFord(int source, int target, int size) {
    // Size is the number of vertices
    int[] prev = new int[size], cur = new int[size];
    Arrays.fill(prev, Integer.MAX_VALUE);
    Arrays.fill(cur, Integer.MAX_VALUE);
    prev[source] = 0;
    for (int i = 0; i < size; i++) { // V passes
      cur[source] = 0;
      for (int[] edge : edges) {
        int src = edge[0], tar = edge[1], weight = edge[2];
        if (cur[src] != Integer.MAX_VALUE && prev[src] + weight < cur[tar]) {
          cur[tar] = prev[src] + weight;
        }
      }
      prev = cur.clone();
    }
    return cur[target] == Integer.MAX_VALUE ? -1 : cur[target]; // Shortest dist: (source -> target)
  }
}

• Time: O(EV)

• Space: O(V)

• Can also work with negative weights but cannot work with negative cycles.

• While Dijkstra uses a Priority Queue to greedily select the closest non-processed vertex, bellman-ford simply relaxes all edges leaving any vertex in any order.

Bellman-Ford with Queue (Shortest Faster Path Algorithm)

class Example {
  Map<Integer, List<int[]>> G; // source: list of [target, weight]

  int spfa(int source, int target) {
    int[] dist = new int[G.size()];
    boolean[] inQueue = new boolean[G.size()];
    Arrays.fill(dist, Integer.MAX_VALUE);
    dist[source] = 0;
    Queue<Integer> queue = new LinkedList<>();
    queue.add(source);
    inQueue[source] = true;

    while (!queue.isEmpty()) {
      int v = queue.remove();
      inQueue[v] = false;
      if (!G.containsKey(v)) continue; // No edges
      for (int[] edge : G.get(v)) {
        int w = edge[1], weight = edge[2];
        if (dist[w] > dist[v] + weight) {
          dist[w] = dist[v] + weight;
          if (!inQueue[w]) queue.add(w);
          inQueue[w] = true;
        }
      }
    }

    return dist[target] == Integer.MAX_VALUE ? -1 : dist[target];
  }
}

• Time: O(EV)

• Space: O(V)

• Cannot be used to calculate the shortest path for at most k passes.