-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathDijkstra Algorithm using priority queue
More file actions
68 lines (59 loc) · 2.43 KB
/
Dijkstra Algorithm using priority queue
File metadata and controls
68 lines (59 loc) · 2.43 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
Given an undirected, weighted graph with V vertices numbered from 0 to V-1 and E edges, represented by 2d array edges[][],
where edges[i]=[u, v, w] represents the edge between the nodes u and v having w edge weight.
You have to find the shortest distance of all the vertices from the source vertex src, and return an array of integers
where the ith element denotes the shortest distance between ith node and source vertex src.
Note: The Graph is connected and doesn't contain any negative weight edge.
Example 1:
Input: V = 3, edges[][] = [[0, 1, 1], [1, 2, 3], [0, 2, 6]], src = 2
Output: [4, 3, 0]
Explanation:
Shortest Paths:
For 2 to 0 minimum distance will be 4. By following path 2 -> 1 -> 0
For 2 to 1 minimum distance will be 3. By following path 2 -> 1
For 2 to 2 minimum distance will be 0. By following path 2 -> 2
Example 2:
Input: V = 5, edges[][] = [[0, 1, 4], [0, 2, 8], [1, 4, 6], [2, 3, 2], [3, 4, 10]], src = 0
Output: [0, 4, 8, 10, 10]
Explanation:
Shortest Paths:
For 0 to 1 minimum distance will be 4. By following path 0 -> 1
For 0 to 2 minimum distance will be 8. By following path 0 -> 2
For 0 to 3 minimum distance will be 10. By following path 0 -> 2 -> 3
For 0 to 4 minimum distance will be 10. By following path 0 -> 1 -> 4
-----------------------------------------------------------------------------------------------------------------------------
// tc=O(E log V)
// User Function Template
class Solution {
public:
vector<int> dijkstra(int V, vector<vector<int>> &edges, int src) {
// Code here
vector<vector<pair<int,int>>>adjList(V);
for(auto it: edges){
int u=it[0];
int v=it[1];
int weight=it[2];
adjList[u].push_back({v,weight});
}
priority_queue<pair<int,int>,vector<pair<int,int>>, greater<pair<int,int>>>pq;
vector<int>dist(V);
for(int i=0;i<V;i++){
dist[i]=1e9;
}
pq.push({0,src});
dist[src]=0;
while(!pq.empty()){
int node=pq.top().second;
int weight=pq.top().first;
pq.pop();
for(auto it:adjList[node]){
int val=it.first;
int w=it.second;
if(weight+w<dist[val]){
dist[val]=weight+w;
pq.push({dist[val], val});
}
}
}
return dist;
}
};