Weighted Graph Shortest Hop Counter
Problem Description
You are given an undirected graph with `n` nodes (labeled `1` to `n`) and a list of connections `linkList` where `linkList[i] = [nodeA, nodeB, cost]` represents an undirected edge between `nodeA` and `nodeB` with a given travel cost.
You are also given a `startNode` and an `endNode`. Find the minimum **number of edges** (hops) needed to travel from `startNode` to `endNode`. If no path exists, return `-1`.
**Note:** Edge weights are irrelevant — only the hop count matters.
**Example 1:**
```
Input: n = 5, linkList = [[1,2,3],[1,3,1],[2,4,7],[3,4,2],[4,5,1]], startNode = 1, endNode = 5
Output: 3
Explanation: Path 1→3→4→5 uses 3 hops.
```
**Example 2:**
```
Input: n = 4, linkList = [[1,2,5],[2,3,5]], startNode = 1, endNode = 4
Output: -1
Explanation: Node 4 is unreachable from node 1.
```
Constraints
- 1 <= n <= 1000
- 0 <= linkList.length <= 5000
- linkList[i].length == 3
- 1 <= nodeA, nodeB <= n
- nodeA != nodeB
- 1 <= cost <= 10^6
- 1 <= startNode, endNode <= n
Follow-up
Now find the minimum total cost path (sum of edge weights) from startNode to endNode — use Dijkstra's algorithm.
Hints
Try the problem first. If you get stuck, you can reveal hints one at a time.
Solution
Leaderboard
No entries yet for python.
Be the first — submit an accepted solution.