Shortest Paths

Bellman Ford

Relax each edge N-1 times.

class Solution {
  public:
    vector<int> bellmanFord(int V, vector<vector<int>>& edges, int src) {
        vector<int> d(V, 1e8);
        d[src] = 0;
        for (int i = 0; i < V-1; i++) {
            for (auto edge: edges) {
                int from = edge[0];
                int to = edge[1];
                int weight = edge[2];
                if (d[from] != 1e8 && d[from]+weight < d[to]) {
                    d[to] = d[from]+weight;
                }
            }
        }
        for (auto edge: edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            if (d[from] != 1e8 && d[from]+weight < d[to]) {
                return {-1};
            }
        }
        return d;
    }
};
 

Dijkstra

Verified here: https://www.geeksforgeeks.org/problems/implementing-dijkstra-set-1-adjacency-matrix/1

class Solution {
  public:
    vector<int> dijkstra(int n, vector<vector<int>> &edges, int src) {
        // Code here
        vector<int> dist(n, INT_MAX);
        priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
        vector<vector<pair<int,int>>> graph(n);
        for (auto edge: edges) {
            int from = edge[0];
            int to = edge[1];
            int weight = edge[2];
            graph[from].push_back({to, weight});
            graph[to].push_back({from, weight});
        }
        dist[src] = 0;
        pq.push({dist[src], src});
        while(!pq.empty()) {
            auto [curWeight, curNode] = pq.top();
            pq.pop();
            if (curWeight != dist[curNode]) {
                continue;
            }
            for (auto next: graph[curNode]) {
                auto [to, weight] = next;
                if (dist[curNode]+weight < dist[to]) {
                    dist[to] = dist[curNode]+weight;
                    pq.push({dist[to], to});
                }
            }
        }
        return dist;
    }
};