Shortest Path Algorithms
Start Timer
0:00:00
You are given a graph, which is implemented as a 2D array. Each cell in the array represents a node and the value in the cell represents the cost to traverse to that node. You are also given a start node and an end node. Your task is to implement a function that finds the shortest path from the start node to the end node using any shortest path algorithm.
Example 1:
Input:
graph = [[0, 4, 0, 0, 0, 0, 0, 8, 0],
[4, 0, 8, 0, 0, 0, 0, 11, 0],
[0, 8, 0, 7, 0, 4, 0, 0, 2],
[0, 0, 7, 0, 9, 14, 0, 0, 0],
[0, 0, 0, 9, 0, 10, 0, 0, 0],
[0, 0, 4, 14, 10, 0, 2, 0, 0],
[0, 0, 0, 0, 0, 2, 0, 1, 6],
[8, 11, 0, 0, 0, 0, 1, 0, 7],
[0, 0, 2, 0, 0, 0, 6, 7, 0]]
start = 0
end = 4
Output:
shortest_path(graph, start, end) -> [0, 1, 2, 5, 6, 7, 8, 4]
Example 2:
Input:
graph = [[0, 5, 0, 9, 1],
[5, 0, 3, 0, 2],
[0, 3, 0, 0, 0],
[9, 0, 0, 0, 0],
[1, 2, 0, 0, 0]]
start = 0
end = 2
Output:
shortest_path(graph, start, end) -> [0, 4, 1, 2]
Recommended questions for you
Personalized based on your user activity, skill level, and preferences.
.
.
.
.
.
.
.
.
.
Comments