Sponsored
Sponsored
Dijkstra's Algorithm is a greedy algorithm used to find the shortest path from a single source node to all other nodes in a weighted graph with non-negative weights. We can adapt it to efficiently find the shortest path for this problem.
Time Complexity: O(V^2), where V is the number of vertices since we're using an adjacency matrix and no priority queue to obtain the minimum distance vertex.
Space Complexity: O(V^2) due to the adjacency matrix storage requirements.
1#include <iostream>
2#include <vector>
3#include <queue>
4#include <limits>
5using namespace std;
6
7class Graph {
8public:
9 int n;
10 vector<vector<pair<int, int>>> adj;
11
12 Graph(int n, vector<vector<int>>& edges) : n(n) {
13 adj.resize(n);
14 for (const auto& edge : edges) {
15 adj[edge[0]].emplace_back(edge[1], edge[2]);
16 }
17 }
18
19 void addEdge(vector<int> edge) {
20 adj[edge[0]].emplace_back(edge[1], edge[2]);
21 }
22
23 int shortestPath(int node1, int node2) {
24 vector<int> dist(n, numeric_limits<int>::max());
25 dist[node1] = 0;
26 priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
27 pq.emplace(0, node1);
28
29 while (!pq.empty()) {
30 auto [curDist, u] = pq.top(); pq.pop();
31
32 if (u == node2) return curDist;
33 if (curDist > dist[u]) continue;
34
35 for (auto [v, cost] : adj[u]) {
36 if (dist[u] + cost < dist[v]) {
37 dist[v] = dist[u] + cost;
38 pq.emplace(dist[v], v);
39 }
40 }
41 }
42 return -1;
43 }
44};
45
46int main() {
47 vector<vector<int>> edges = {{0, 2, 5}, {0, 1, 2}, {1, 2, 1}, {3, 0, 3}};
48 Graph* g = new Graph(4, edges);
49 cout << g->shortestPath(3, 2) << endl; // Output: 6
50 cout << g->shortestPath(0, 3) << endl; // Output: -1
51 g->addEdge({1, 3, 4});
52 cout << g->shortestPath(0, 3) << endl; // Output: 6
53 delete g;
54 return 0;
55}The C++ implementation employs a priority queue to facilitate the efficient checking of the next node to visit, which ensures better optimization of the Dijkstra algorithm for pathfinding.
The Floyd-Warshall Algorithm is a dynamic programming algorithm used to find shortest paths between all pairs of vertices in a weighted graph. This approach is more suited when there are frequent shortest path queries between multiple different node pairs.
Time Complexity: O(n^3), where n is the number of vertices, arising from the three nested loops.
Space Complexity: O(n^2) due to the distance matrix storage covering all node pairs.
This implementation uses Floyd-Warshall Algorithm, which precomputes shortest paths between all pairs of nodes. Post addEdge operations, the algorithm recomputes paths by potentially updating the distance matrix.