Weighted Shortest Path

visualgo

Dijkstra’s Algorithm (implementation)

https://cp-algorithms.com/graph/dijkstra.html

const int INF = 1000000000;
vector<vector<pair<int, int>>> adj;

void dijkstra(int s, vector<int> & d, vector<int> & p) {
    int n = adj.size();
    d.assign(n, INF);
    p.assign(n, -1);
    vector<bool> u(n, false);

    d[s] = 0;
    for (int i = 0; i < n; i++) {
        int v = -1;
        for (int j = 0; j < n; j++) {
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        }

        if (d[v] == INF)
            break;

        u[v] = true;
        for (auto edge : adj[v]) {
            int to = edge.first;
            int len = edge.second;

            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}

• https://grader.mwit.ac.th/problem/turboprogramming dijkstra ตรงๆ

  // credit Mok MWIT29
  #include <bits/stdc++.h>
  #define ii pair<int, int>
  using namespace std;
  vector<ii> adj[100100];
  int dist[100100];
  int main() {
    int N, M, Q;
    scanf("%d %d %d", &N, &M, &Q);
    for (int i = 1, u, v, w; i <= M; i++) {
      scanf("%d %d %d", &u, &v, &w);
      adj[u].push_back(make_pair(v, w));
      // adj[v].push_back(make_pair(u, w));
    }
    for (int i = 1; i <= N; i++)
      dist[i] = INT_MAX;
    priority_queue<ii, vector<ii>, greater<ii>> pq;
    dist[1] = 0;
    pq.push(make_pair(0, 1));
    while (!pq.empty()) {
      int d = pq.top().first;
      int n = pq.top().second;
      pq.pop();
      for (auto x : adj[n]) {
        if (dist[x.first] > d + x.second) {
          dist[x.first] = d + x.second;
          pq.push(make_pair(d + x.second, x.first));
        }
      }
    }
    while (Q--) {
      int a;
      scanf("%d", &a);
      if (dist[a] == INT_MAX)
        printf("-1\n");
      else
        printf("%d\n", dist[a]);
    }
  }

• https://grader.mwit.ac.th/problem/town dijsktra ไม่ตรงมาก
• https://grader.mwit.ac.th/problem/followpeatt dijkstra แบบมีเงื่อนไข
• https://grader.mwit.ac.th/problem/toi14_logistics dijkstra ซับซ้อนขึ้น

Bellman-Ford

• Negative cycles

// credit from https://github.com/Autoratch/practice
#include <bits/stdc++.h>
using namespace std;

int n, m, s, e;
vector<pair<int, pair<int, int>>> adj;
vector<int> dist;

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  cin >> n >> m >> s >> e;

  adj.resize(m);
  dist.assign(n, INT_MAX);

  for (int i = 0; i < m; i++) {
    int a, b, d;
    cin >> a >> b >> d;
    adj[i] = {d, {a, b}};
  }

  dist[0] = 0;
  for (int i = 0; i < n - 1; i++)
    for (int j = 0; j < m; j++) {
      int a = adj[i].second.first, b = adj[i].second.second, d = adj[i].first;
      if (dist[a] != INT_MAX and dist[a] + d < dist[b])
        dist[b] = dist[a] + d;
    }

  cout << dist[e];
}

Floyd-Warshall (implementation)

https://cp-algorithms.com/graph/all-pair-shortest-path-floyd-warshall.html

for (int k = 0; k < n; ++k) {
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            d[i][j] = min(d[i][j], d[i][k] + d[k][j]); 
        }
    }
}

• https://grader.mwit.ac.th/problem/toi17_1221 all-pair

Johnson (exist)

A* Search

https://www.redblobgames.com/pathfinding/a-star/introduction.html