Bnsf Railway Interview Questions

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]