Optimizing a dijkstra implementation

Question

QUESTION EDITED, now I only want to know if a queue can be used to improve the algorithm.

I have found this implementation of a mix cost max flow algorithm, which uses dijkstra: http://www.stanford.edu/~liszt90/acm/notebook.html#file2

Gonna paste it here in case it gets lost in the internet void:

// Implementation of min cost max flow algorithm using adjacency
// matrix (Edmonds and Karp 1972).  This implementation keeps track of
// forward and reverse edges separately (so you can set cap[i][j] !=
// cap[j][i]).  For a regular max flow, set all edge costs to 0.
//
// Running time, O(|V|^2) cost per augmentation
//     max flow:           O(|V|^3) augmentations
//     min cost max flow:  O(|V|^4 * MAX_EDGE_COST) augmentations
//     
// INPUT: 
//     - graph, constructed using AddEdge()
//     - source
//     - sink
//
// OUTPUT:
//     - (maximum flow value, minimum cost value)
//     - To obtain the actual flow, look at positive values only.

#include <cmath>
#include <vector>
#include <iostream>

using namespace std;

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long L;
typedef vector<L> VL;
typedef vector<VL> VVL;
typedef pair<int, int> PII;
typedef vector<PII> VPII;

const L INF = numeric_limits<L>::max() / 4;

struct MinCostMaxFlow {
  int N;
  VVL cap, flow, cost;
  VI found;
  VL dist, pi, width;
  VPII dad;

  MinCostMaxFlow(int N) : 
    N(N), cap(N, VL(N)), flow(N, VL(N)), cost(N, VL(N)), 
    found(N), dist(N), pi(N), width(N), dad(N) {}

  void AddEdge(int from, int to, L cap, L cost) {
    this->cap[from][to] = cap;
    this->cost[from][to] = cost;
  }

  void Relax(int s, int k, L cap, L cost, int dir) {
    L val = dist[s] + pi[s] - pi[k] + cost;
    if (cap && val < dist[k]) {
      dist[k] = val;
      dad[k] = make_pair(s, dir);
      width[k] = min(cap, width[s]);
    }
  }

  L Dijkstra(int s, int t) {
    fill(found.begin(), found.end(), false);
    fill(dist.begin(), dist.end(), INF);
    fill(width.begin(), width.end(), 0);
    dist[s] = 0;
    width[s] = INF;

    while (s != -1) {
      int best = -1;
      found[s] = true;
      for (int k = 0; k < N; k++) {
        if (found[k]) continue;
        Relax(s, k, cap[s][k] - flow[s][k], cost[s][k], 1);
        Relax(s, k, flow[k][s], -cost[k][s], -1);
        if (best == -1 || dist[k] < dist[best]) best = k;
      }
      s = best;
    }

    for (int k = 0; k < N; k++)
      pi[k] = min(pi[k] + dist[k], INF);
    return width[t];
  }

  pair<L, L> GetMaxFlow(int s, int t) {
    L totflow = 0, totcost = 0;
    while (L amt = Dijkstra(s, t)) {
      totflow += amt;
      for (int x = t; x != s; x = dad[x].first) {
        if (dad[x].second == 1) {
          flow[dad[x].first][x] += amt;
          totcost += amt * cost[dad[x].first][x];
        } else {
          flow[x][dad[x].first] -= amt;
          totcost -= amt * cost[x][dad[x].first];
        }
      }
    }
    return make_pair(totflow, totcost);
  }
};

My question is if it can be improved by using a priority queue inside of Dijkstra(). I tried but I couldn't get it to work properly. Actually I suspect that in Dijkstra it should be looping over adjacent nodes, not all nodes...

Thanks a lot.

Answer 1

I am not so sure using a priority queue to implement Dijkstra's algorithm will actually improve the run time because, while using a priority queue decreases the amount of time needed to find the vertex with minimum distance from the source (O(log V) with a priority queue vs. O(V) in the naive implementation), it also increases the amount of time needed to process a new edge (O(log V) with a priority queue vs. O(1) in the naive implementation).

Thus, for the naive implementation, the running time is O(V^2+E).

However, for the priority queue implementation, the running time is O(V log V+E log V).

For very dense graphs, E could be O(V^2), which means the naive implementation would have running time O(V^2+V^2)=O(V^2) while the priority queue implementation would have running time O(V log V+V^2 log V)=O(V^2 log V). Thus, as you can see, the priority queue implementation actually has a worse worst-case run time in the case of dense graphs.

Given the fact that the people writing the above implementation stored the edges as an adjacency matrix rather than using adjacency lists, it looks like the people who wrote this code were expecting the graph to be a dense graph with O(V^2) edges, so it makes sense that they would use the naive implementation over the priority queue implementation here.

For more info about running time of Dijkstra's algorithm, read up on this Wikipedia page.

Answer 2

Surely Dijkstra's algorithm can be improved by using minheap. After we put a vertex into shortest-path tree and process (i.e. label) all adjacent vertices, our next step is to select the vertex with smallest label, not yet in the tree.
This is where minheap comes to mind. Rather than sequentially scan through all vertices, we extract the min element from heap and restructure it, which takes O(logn) time vs O(n). Note that the heap is going to keep only those vertices that are not yet in the shortest-path tree. However we should be able to somehow modify vertices in the heap, if we update their labels.