Implement Dijkstra’s Algorithm | Dataford Interview Questions

Write a function to implement a specific algorithm, for example Dijkstra’s algorithm.

Implement dijkstra(graph, start) for a directed graph represented as {node: [[neighbor, weight], ...]}. Return a dictionary containing the shortest distance from start to every node, using None for unreachable nodes. Edge weights are nonnegative, and every node appears as a key in graph.

Constraints

1 <= number of nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
0 <= weight <= 10^9
All edge endpoints appear as keys in graph
All node identifiers are comparable when stored in the heap
The graph is directed and edge weights are nonnegative

Function Signature

def dijkstra(graph, start):

Your question is Implement Dijkstra’s Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Write a function to implement a specific algorithm, for example Dijkstra’s algorithm.

Constraints

1 <= number of nodes <= 10^5
0 <= number of directed edges <= 2 * 10^5
0 <= weight <= 10^9
All edge endpoints appear as keys in graph
All node identifiers are comparable when stored in the heap
The graph is directed and edge weights are nonnegative

Function Signature

def dijkstra(graph, start):

Your question is Implement Dijkstra’s Algorithm. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.