Risky Edges in Graph.md

Solution

Algorithm

1. Let G' = (V, E - E')
2. Create h + 1 copies of G' as G₀, ... G_h
3. if (u, v) is a risky edge in G, include a directed edge from u in G_i to v in G_i+1
4. Run Dijkstra's Algorithm from start vertex s. Now dijstraDistance(s, v_i) represents shortest path from s to v in original graph G using exactly i risky edges.
5. To calculate our solution (the distance from s to v in original graph G using at most h risky edges), we calculate: minimum_0<=i<=h { dijkstraDistance(s, v_i) }.

Time/Space Complexity

• Time Complexity: Dijkstra's algorithm is generally O(m + n log n), but since we have mh edges and nh nodes, our complexity becomes O(mh + nh log (nh))
• Space Complexity: O(mh + nh) to create G'

Follow-up Solution

Use the same algorithm as above, but instead of creating h + 1 copies of G', extend it to create h_ih_j + 1 copies of G', where the h_ih_j copy represents having traversed i blue edges and j red edges.

Time/Space Complexity

Same as above, but replace each h with h_ih_j