Skip to main content

Weighted Graph Shortest Hop Counter

medium
GraphDepth First SearchBreadth First SearchGraph Bfs Shortest Path
Asked atAmazonGoogleMetaUber

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.