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:

<pre tabindex="0" class="chroma"><code>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
</code></pre>

Output:

<pre tabindex="0" class="chroma"><code>shortest_path(graph, start, end) -&gt; [0, 1, 2, 5, 6, 7, 8, 4]
</code></pre>

Example 2:

Input:

<pre tabindex="0" class="chroma"><code>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
</code></pre>

Output:

<pre tabindex="0" class="chroma"><code>shortest_path(graph, start, end) -&gt; [0, 4, 1, 2]
</code></pre>

The task is to implement a shortest path algorithm (like Dijkstra's or Bellman-Ford) to find the shortest path from a start node to an end node in a given graph. The graph is represented as a 2D array where each cell represents a node and the value in the cell represents the cost to traverse to that node.

Shortest Path Algorithms

Comments