# Given a source and destination, find the path with minimum stress level in a Graph

I faced this problem in a hiring challenge which is now over. I wrote a solution for the problem but at that time the judge gave me wrong answer. Afterwords I thought about the solution but couldn't find any problem with my logic. Maybe I made some implementation mistake during the contest (I'm not sure). But now I have my solution and I don't know if it's correct or not. I have tried it on multiple graphs and it gives correct answer on all of them. But yes a single case is enough to prove an algorithm wrong. So below I provide the details. Please help me validate the solution.

Problem Given an un-directed graph (can be disconnected) with N nodes and E edges. The stress level of the path is defined as the maximum weight of an edge present on this path. Given a source U and destination V you need to tell the minimum stress level from node U to node V. If you cannot reach V from U, return -1.

My Solution

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int mod = 1e9 + 7;

int minStressLevel(vector<vector<pair<int, int> > > &adj, set<pair<int, int> >
&visited, int src, int dst) {
if(src == dst) return 0;

int ans = INT_MAX;
int v = to.first;
int w = to.second;

if(!visited.count({dst, v})) {
visited.insert({dst, v});
visited.insert({v, dst});
ans = min(ans, max(minStressLevel(adj, visited, src, v), w));
}
}

return ans;
}

int32_t main() {
int t;
cin >> t;

for(int d = 0; d < t; d++) {
int n, e;
cin >> n >> e;

vector<vector<pair<int, int> > > adj(n + 1);

for(int i = 0; i < e; i++) {
int u, v, w;
cin >> u >> v >> w;

}

vector<int> dp(n + 1, INT_MAX);
set<pair<int, int> > visited;

int source, destination;
cin >> source >> destination;

int ans = minStressLevel(adj, visited, source, destination);
cout << "Case #" << d << ": ";
if(ans == INT_MAX) cout << -1 << endl;
else cout << ans << endl;
}
}


Explanation The solution is based on this recurrence: minStressLevel(V) = min{max(minStressLevel(K), edge_weight(K, V))} over all neighbours K of V.

I keep a set of pairs to keep track of what edges have been visited so that I don't get into infinite loops. This is different than a simple Breadth First Search where we stop once we discover a vertex and do not visit it again.

Time Complexity I think time complexity is O(E), where E is the number of edges. Constraints N <= 1e5 E <= 1e5 edge_weight <= 1e9

• Checking your code is off-topic here. Coding questions are off-topic here, and not everyone knows C++, so we request people to use concise pseudocode rather than providing code.
– D.W.
Oct 11, 2021 at 4:45

One solution that could work in $$O(m \log m)$$ time is to binary search for the stress level and do BFS on only edges with lower weight.