( Down the variations, we will use sets, priority queues, multisets in Dijkstra's algorithm to broaden your knowledge )
The shortest path problem is about finding a path between 2 vertices in a graph such that the total sum of the edges' weights is minimum.
This problem could be solved easily using (BFS) if all edge weights were (1), but here weights can take any value.
So, to solve that problem, we will use:
Dijkstra's Algorithm
Dijkstra's algorithm has many variants but the most common one is to find the shortest paths from the source vertex to all other vertices in the graph.
Algorithm:
- Set all vertices distances = infinity except for the source vertex, set the source distance = .
- Push the source vertex in a min-priority queue in the form (distance, vertex), as the comparison in the min-priority queue will be according to vertices distances.
- Pop the vertex with the minimum distance from the priority queue (at first the popped vertex = source).
- Update the distances of the connected vertices to the popped vertex in case of "current vertex distance + edge weight < next vertex distance", then push the vertex
with the new distance to the priority queue. - Apply the same algorithm again until the priority queue is empty.
Aim: We want a distance(dist[ ]) array, which will store the shortest path distance for each node, from the source node.
Let's understand each line of the algorithm with code, before that we initialise a few variables, globally in our program.
#define ll long long int // long long
#define pii pair<long long int, long long int> // a pair
#define pb push_back
#define fi first // to get the value of first element in a pair
#define ss second // to get the value of second element in a pair
const int Nmax = 2e5;
long long int INF=1e15;
vector<pii> adj[Nmax]; // adjacency list
ll dist[Nmax]; // Distance array
Line 1)
We make a Reset() function, in which we initialise the distance array with INF.
void Reset()
{
memset(dist,INF,sizeof(dist)); // Initialized with infinity
}
Line 2)
We will make a Dijkstra function, in which we initialise our Min-heap, pushed the first node with the distance of source node(dist[source]) to be zero.
priority_queue<pii,vector<pii>,greater<pii>> pq; // Min-heap
pq.push({0,src}); // pushed a pair, {distance,node}
dist[src]=0; // Source distance to be zero
So, now we can write the whole code according to Line 3,4,5 in code as:
(Finalize)
Dijkstra
void Reset()
{
memset(dist,INF,sizeof(dist));
}
void dijkstra(ll src, ll dest)
{
priority_queue<pii,vector<pii>,greater<pii>> pq;
pq.push({0,src});
dist[src]=0;
while(!pq.empty())
{
ll u = pq.top().ss; // top node of the minheap
pq.pop();
for(auto v : adj[u]) // traversing through his neighbours
{
if(dist[v.fi] > dist[u] + v.ss) // Distance will be updated here
{
dist[v.fi] = dist[u] + v.ss;
pq.push({dist[v.fi],v.fi});
}
}
}
}
Note: Here, we don't need a visited array as we only update a distance, when we find a smaller distance value than previous value so, it won't update it.
Time Complexity of Dijkstra's Algorithm with Min-heap : O(V + E*logV)
This Algorithm works for both directed and undirected graph but fails for the negative edges.
Variations:
1. Path with Minimum Xor sum of edges in a directed graph:
Algo:
Code:
Iterate all the nodes adjacent to the current node and push into the priority queue and their distance as XOR sum with the current distance and edge weight.
Code:
(We can also use Visited array and Set(will work as minheap) here, you can also use the previous code to do the same)
set<pair<ll, ll> > pq;
pq.insert({0,src});
// Visited array
bool v[Nmax] = {0};
// While the priority-queue
// is not empty
while (!pq.empty())
{
// Current node
ll curr = pq.begin()->second;
// Current xor sum of distance
ll dist = pq.begin()->first;
// Popping the top-most element
pq.erase(pq.begin());
// If already visited continue
if (v[curr])
continue;
// Marking the node as visited
v[curr] = 1;
// If it is a destination node
if (curr == d)
return dist;
// Traversing the current node
for (auto it : gr[curr])
pq.insert({ dist ^ it.second,it.first });
}
2 . Path with the smallest product of edges with weight >=1:
Algo:
Same code as above with a slight variation, distance=1, will be pushed rather than distance=0.
pq.insert({1,src}).
3. Widest Path Problem: find a path between two vertices of the graph maximizing the weight of the minimum-weight edge in the path:
In the practical application, this problem can be seen as a graph with routers as its vertices and edges represent bandwidth between two vertices. Now if we want to find the maximum bandwidth path between two places in the internet connection, then this problem can be solved by this algorithm.
Algo:
Let's replace the dist[ ] with widest[ ] array.
The only variation will be in the condition where we update the distance array, previously.
max(min(widest[u], weight(u, v)), widest[v])
Code:
int widest_path_problem(vector<vector<pair<int, int> > >& Graph,
int src, int target)
{
// widest distance
vector<int> widest(Graph.size(), INT_MIN);
// To get the path at the end of the algorithm
vector<int> parent(Graph.size(), 0);
priority_queue<pair<int, int>, vector<pair<int, int> >,
greater<pair<int, int> > >
container;
container.push(make_pair(0, src));
widest[src] = INT_MAX;
while (container.empty() == false) {
pair<int, int> temp = container.top();
int current_src = temp.second;
container.pop();
for (auto vertex : Graph[current_src]) {
int distance = max(widest[vertex.second],
min(widest[current_src], vertex.first));
if (distance > widest[vertex.second]) {
widest[vertex.second] = distance;
parent[vertex.second] = current_src;
container.push(make_pair(distance, vertex.second));
}
}
}
return widest[target];
}
4. Minimum cost path from the source node to the destination node via an intermediate node ( If an edge is travelled twice, only once the weight is calculated as cost ):
Algo:
Take a path Path1 from Source to intermediate, and a path Path2 from intermediate to destination. There can be some common edges among these 2 paths. Hence, the optimal path will always have the following form: for any node U, the walk consists of edges on the shortest path from Source to U, from intermediate to U, and from destination to U. Hence, if dist(a, b) is the cost of the shortest path between node a and b, the required minimum cost path will be min{ dist(Source, U) + dist(intermediate, U) + dist(destination, U) } for all U. The Minimum distance of all nodes from Source, intermediate, and destination can be found from Dijkstra algorithm.
(Here we are using multiset)
Code:
#define MAXN 100005
int dist[MAXN];
void dijkstra(int source, int n)
{
for (int i = 0; i < n; i++)
dist[i] = INT_MAX;
bool vis[n];
memset(vis, false, sizeof vis);
dist = 0;
multiset<pair<int, int> > s;
s.insert({ 0, source });
while (!s.empty()) {
pair<int, int> p = *s.begin();
s.erase(s.begin());
int x = p.second;
int wei = p.first;
if (vis[x])
continue;
vis[x] = true;
for (int i = 0; i < v[x].size(); i++) {
int e = v[x][i].first;
int w = v[x][i].second;
if (dist[x] + w < dist[e]) {
dist[e] = dist[x] + w;
s.insert({ dist[e], e });
}
}
}
}
int solve(int source, int destination,
int intermediate, int n)
{
int ans = INT_MAX;
dijkstra(source, n);
int dsource[n];
for (int i = 0; i < n; i++)
dsource[i] = dist[i];
dijkstra(destination, n);
// distance from destination
// to all other vertices
int ddestination[n];
for (int i = 0; i < n; i++)
ddestination[i] = dist[i];
dijkstra(intermediate, n);
// distance from intermediate
// to all other vertices
int dintermediate[n];
for (int i = 0; i < n; i++)
dintermediate[i] = dist[i];
// required answer
for (int i = 0; i < n; i++)
ans = min(ans, dsource[i] + ddestination[i]
+ dintermediate[i]);
return ans;
}
Comments
Post a Comment