Programming Challenge: Implementing Dijkstra's
In this lesson, you'll be implementing Dijkstra's Shortest Path Algorithm.
We'll cover the following
Problem Statement
Given an adjacency matrix in a 2D array, solve the Single Source Shortest Path algorithm, essentially by implementing the Dijkstra’s algorithm discussed in the previous lesson. We’ve written some skeleton code for the function.
- The value of the weight of the link is
graph[src][dst]
. - The graph is undirected so
graph[src][dst]==graph[dst][src]
. - A link between the
src
anddst
exists if-1<graph[src][dst]<16
. - If
graph[src][dst]>=16
the weight of the link is infinite and it does not function.
Input
- An adjacency matrix, i.e., a 2D array, a source node, and a destination node.
Output
The shortest path between the source and destination in the form of an array of integers where each integer represents a node and the total weight of the path.
Get hands-on with 1200+ tech skills courses.