Shortest Paths Algorithms

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <iostream>
#include <queue>
#include <unordered_map>
#include <vector>

using namespace std;

/**
 * compute shortest distance from src to all other nodes
 */
void dijkstra(const vector<unordered_map<int, int>>& G, int src,
              vector<int>& dist) {
  int n = G.size();
  dist.clear();
  dist.resize(n, -1);
  vector<bool> vis(n);
  priority_queue<pair<int, int>> pq;  // {-weight, label}
  pq.emplace(0, src);
  dist[src] = 0;
  while (!pq.empty()) {
    auto p = pq.top();
    pq.pop();
    vis[p.second] = true;
    for (auto neighbor : G[p.second]) {
      int v = neighbor.first;
      int d = neighbor.second - p.first;
      if (vis[neighbor.first]) continue;
      if (dist[v] == -1 || dist[v] > d) {
        pq.emplace(-d, v);
        dist[v] = d;
      }
    }
  }
}

template <typename T>
void printArr(const vector<T>& arr) {
  for (const T& t : arr) cout << t << " ";
  cout << endl;
}

int main(int argc, char const* argv[]) {
  vector<vector<int>> edges = {
      {0, 1, 100}, {1, 2, 100}, {0, 2, 500}};  // {src, dst, weight}, ...
  int N = 3;
  vector<unordered_map<int, int>> G(N);
  for (const auto& edge : edges) {
    G[edge[0]][edge[1]] = edge[2];
  }
  vector<int> dist;
  int src = 0;
  dijkstra(G, src, dist);
  printArr(dist);
  return 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

bool solve() {
  int n, m, START = 1;
  cin >> n >> m;
  // read graph
  vector<unordered_map<int, int>> graph(n + 1);
  for (int i = 0; i < m; ++i) {
    int s, t, w;
    cin >> s >> t >> w;
    graph[s][t] = graph[s].count(t) ? min(w, graph[s][t]) : w;
    if (w >= 0) {
      graph[t][s] = graph[t].count(s) ? min(w, graph[t][s]) : w;
    }
  }

  // the order (0 indexed) of a shortest path, if >= n, then negative cycle detected
  vector<int> cnt(n + 1);
  vector<int> dist(n + 1, INT32_MAX);
  dist[START] = 0;

  priority_queue<int> q;
  q.push(START);
  vector<bool> in_queue(n);
  while (!q.empty()) {
    int source = q.top();
    q.pop();
    in_queue[source] = false;
    // iterate through all neighbors
    for (auto neighborWeight: graph[source]) {
      // relaxation
      if (neighborWeight.second + dist[source] < dist[neighborWeight.first]) {
        dist[neighborWeight.first] = neighborWeight.second + dist[source];
        cnt[neighborWeight.first] = cnt[source] + 1;
        if (cnt[neighborWeight.first] >= n) {
          // loop detected
          return true;
        }
        if (!in_queue[neighborWeight.first]) {
          in_queue[neighborWeight.first] = true;
          q.push(neighborWeight.first);
        }
      }
    }
  }
  return false;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45

// https://www.luogu.com.cn/problem/B3647
void solve() {
  // number of nodes and edges
  int n, m;
  cin >> n >> m;

  // all positive weights, use -1 to indicate no edge
  vector<vector<int>> G(n, vector<int>(n, NO_EDGE));
  vector<vector<int>> prev(n, vector<int>(n));

  for (int i = 0; i < n; ++i) {
    G[i][i] = 0;
  }
  for (int i = 0; i < m; ++i) {
    int from, to, weight;
    cin >> from >> to >> weight;
    --from;
    --to;
    G[from][to] = min(weight, G[from][to]);
    prev[from][to] = from;
    // non directed
    G[to][from] = min(weight, G[to][from]);
    prev[to][from] = to;
  }

  // floyd
  for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < n; ++j) {
        if (G[i][k] != NO_EDGE && G[k][j] != NO_EDGE &&
            (G[i][j] == NO_EDGE || G[i][j] > G[i][k] + G[k][j])) {
          G[i][j] = G[i][k] + G[k][j];
          prev[i][j] = prev[k][j];
        }
      }
    }
  }

  for (int i = 0; i < n; ++i) {
    for (int j = 0; j < n; ++j) {
      cout << G[i][j] << " ";
    }
    cout << endl;
  }
}