Six Clicks Away
You are a software engineer on YouTube's recommendation team. Your task is to analyze the video recommendation graph — a directed weighted network where each edge [u, v, w] means video u recommends video v with a "distance score" of w (lower is better).
To power the recommendation engine, you need to know the shortest recommendation path between every pair of videos. This lets you answer: "How many hops does it take to get from any video to any other video through the recommendation graph?"
Given n videos and a list of directed weighted edges, return an n×n matrix where result[i][j] is the shortest path from video i to video j. If video j is unreachable from video i, use -1. The distance from any video to itself is 0.
Example 1
(3, [[0,1,10],[0,2,2],[2,1,3]])[[0, 5, 2], [-1, 0, -1], [-1, 3, 0]]0→1 directly costs 10. But 0→2→1 costs 2+3=5. Floyd-Warshall finds the cheaper indirect path.
Example 2
(3, [[0,1,1],[1,2,1],[2,0,1]])[[0, 1, 2], [2, 0, 1], [1, 2, 0]]Fully connected cycle. From any node, all other nodes are reachable with known distances.
Example 3
(4, [[0,1,1],[2,3,1]])[[0, 1, -1, -1], [-1, 0, -1, -1], [-1, -1, 0, 1], [-1, -1, -1, 0]]Two disconnected components. Pairs across components use -1.
- ›1 <= n <= 100
- ›0 <= len(edges) <= 1000
- ›1 <= weight <= 1000
- ›No negative weights
- ›No self-loops
Loading question…