# 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] ;    }};`

--

--