Shortest Path in Weighted Graph
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.
