Floyd–Warshall and Dijkstra algorithm

2642. Design Graph With Shortest Path Calculator

Floyd–Warshall

This is the 4th question of today (April 15, 2023) ’s biweekly LC contest.

We can use Floyd–Warshall algorithm to solve this problem as n is small which is only 100.

Python

class Graph:
    def __init__(self, n: int, edges: List[List[int]]):
        self.n = n
        self.dis = [[float('inf')]*n for _ in range(n)]
        for a,b, c in edges:
            self.dis[a][b]=c
        for i in range(n):self.dis[i][i]=0
        for k in range(n):
            for i in range(n):
                for j in range(n):
                    self.dis[i][j] = min(self.dis[i][j], self.dis[i][k]+self.dis[k][j])

    def addEdge(self, edge: List[int]) -> None:
        k1, k2, c = edge
        for i in range(self.n):
            for j in range(self.n):
                self.dis[i][j] = min(self.dis[i][j], self.dis[i][k1] + c + self.dis[k2][j])

    def shortestPath(self, node1: int, node2: int) -> int:
        if self.dis[node1][node2] == float('inf'):return -1
        return self.dis[node1][node2]

C++ (211ms)

const int INF = 0x3f3f3f3f;
int dis[110][110];
class Graph {
public:
    int n;
    Graph(int n, vector<vector<int>>& edges) {
        this -> n = n;
        memset(dis, 0x3f, sizeof dis);
        for (auto e : edges){
            int i = e[0], j = e[1], c = e[2];
            dis[i][j] = c;
        }
        for (int i = 0; i< n; ++i)dis[i][i] = 0;
            
        for (int k = 0; k < n; ++k)
             for (int i = 0; i < n; ++i)
               for (int j = 0; j < n; ++j)
                      dis[i][j] = min(dis[i][j], dis[i][k]+dis[k][j]);
    }
    void addEdge(vector<int> e) {
        int k1 = e[0], k2 = e[1], c = e[2];
        for (int i = 0; i < n; ++i)
            for (int j = 0; j < n; ++j)
                dis[i][j] = min(dis[i][j], dis[i][k1] + c + dis[k2][j]);
        
        
    }
    
    int shortestPath(int i, int j) {
        return dis[i][j] == INF? -1: dis[i][j];      
    }
};

Dijkstra algorithm

We can also solve it by using Dijkstra algorithm

Naive one (516ms)

typedef  pair<int, int> PII;
const int INF = 0x3f3f3f3f;
class Graph {
public:
vector<vector<PII>> graph;
int n;
    Graph(int n, vector<vector<int>>& edges) {
        this -> n = n;
        graph.resize(n);
        for (auto e: edges)addEdge(e);
    }
    
    void addEdge(vector<int> edge) {
        auto &e = edge;
        graph[e[0]].emplace_back(e[1], e[2]);
    }
    
    int shortestPath(int node1, int node2) {
        vector<int> dis(n, INF);
        dis[node1] = 0;
        set<PII> pq;
        for (int i = 0; i < n; ++i){
            pq.emplace(dis[i], i);
        }
        while (!pq.empty()){
            auto [this_dis, i] = *pq.begin();pq.erase(pq.begin());
            for (auto [j, c]: graph[i]){
                int new_dis_to_j = this_dis + c;
                // if find a shorter path, update: delete old, insert new
                if (new_dis_to_j < dis[j]){
                    pq.erase({dis[j], j}); //as old_dis > this_dis, it must exist in the set.
                    dis[j] = new_dis_to_j;
                    pq.insert({dis[j], j});
                }
            } 
        }
        return dis[node2] == INF? -1:  dis[node2] ;
    }
};

Improved one (387ms)

For the naive one, it is using the set, so we can delete the old one and put the new one to finish the update operation.

typedef  pair<int, int> PII;
const int INF = 0x3f3f3f3f;
class Graph {
public:
vector<vector<PII>> graph;
int n;
    Graph(int n, vector<vector<int>>& edges) {
        graph.resize(n);
        this -> n = n;
        for (auto e: edges)addEdge(e);
    }
    
    void addEdge(vector<int> edge) {
        auto &e = edge;
        graph[e[0]].emplace_back(e[1], e[2]);
    }
    
    int shortestPath(int node1, int node2) {
        vector<int> dis(n, INF);
        dis[node1] = 0;
        priority_queue<PII, vector<PII>, greater<PII>> min_pq;
        for (int i = 0; i < n; ++i){
            min_pq.emplace(dis[i], i);
        }
        while (!min_pq.empty()){
            auto [this_dis, i] = min_pq.top();min_pq.pop();
            // postponed deletion
            if (this_dis > dis[i])continue;
            for (auto [j, c]: graph[i]){
                int new_dis_to_j = this_dis + c;
                if (new_dis_to_j < dis[j]){
                    dis[j] = new_dis_to_j;
                    min_pq.emplace(dis[j], j);
                }
            } 
        }
        return dis[node2] == INF? -1:  dis[node2] ;
    }
};