BudiBadu Logo
00:00

Shortest Path in Weighted Graph

Graph Medium 0 views

Given an undirected weighted graph represented as an adjacency list and two nodes (source and destination), write a function to find the shortest path length between them. Return -1 if no path exists.

Problem Details: The graph is provided as an adjacency list, where each node is associated with a list of pairs (neighbor, weight), indicating the neighboring nodes and the weight of the edges connecting to them. The weights are positive integers, representing the cost or distance of traversing each edge. Your task is to find the minimum total weight of a path from the source node to the destination node. A path is a sequence of nodes connected by edges, and the shortest path is the one with the smallest sum of edge weights. If there is no path between the source and destination nodes, the function should return -1. The solution must account for various graph configurations, including cases where the graph has no edges, or the source and destination are the same node.

Example 1:

Input: n = 5, edges = [[0,1,2], [0,2,4], [1,3,1], [2,3,3], [3,4,5]], source = 0, destination = 4
Output: 8
Explanation: The shortest path is 0 -> 1 -> 3 -> 4, with edge weights 2 + 1 + 5 = 8, which is the minimum total weight to reach node 4 from node 0.

Example 2:

Input: n = 3, edges = [[0,1,1], [1,2,2]], source = 0, destination = 2
Output: 3
Explanation: The shortest path is 0 -> 1 -> 2, with edge weights 1 + 2 = 3, representing the minimum total weight to reach node 2 from node 0.

Example 3:

Input: n = 2, edges = [], source = 0, destination = 1
Output: -1
Explanation: Since there are no edges in the graph, no path exists between nodes 0 and 1, so the function returns -1.

Related Problems

No related problems found

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

BudiBadu Logo

Shortest Path in Weighted Graph

Graph Medium 0 views

Given an undirected weighted graph represented as an adjacency list and two nodes (source and destination), write a function to find the shortest path length between them. Return -1 if no path exists.

Problem Details: The graph is provided as an adjacency list, where each node is associated with a list of pairs (neighbor, weight), indicating the neighboring nodes and the weight of the edges connecting to them. The weights are positive integers, representing the cost or distance of traversing each edge. Your task is to find the minimum total weight of a path from the source node to the destination node. A path is a sequence of nodes connected by edges, and the shortest path is the one with the smallest sum of edge weights. If there is no path between the source and destination nodes, the function should return -1. The solution must account for various graph configurations, including cases where the graph has no edges, or the source and destination are the same node.

Example 1:

Input: n = 5, edges = [[0,1,2], [0,2,4], [1,3,1], [2,3,3], [3,4,5]], source = 0, destination = 4
Output: 8
Explanation: The shortest path is 0 -> 1 -> 3 -> 4, with edge weights 2 + 1 + 5 = 8, which is the minimum total weight to reach node 4 from node 0.

Example 2:

Input: n = 3, edges = [[0,1,1], [1,2,2]], source = 0, destination = 2
Output: 3
Explanation: The shortest path is 0 -> 1 -> 2, with edge weights 1 + 2 = 3, representing the minimum total weight to reach node 2 from node 0.

Example 3:

Input: n = 2, edges = [], source = 0, destination = 1
Output: -1
Explanation: Since there are no edges in the graph, no path exists between nodes 0 and 1, so the function returns -1.

00:00
Loading editor...
Test Results

Run your code to see test results

Click the Submit button to execute your solution

Related Problems

No related problems found

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.