Coding

Dijkstra's algorithm

Asked at

Atlassian

Google

Microsoft

UKG

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The problem

Given a weighted, undirected graph of V vertices, numbered from 0 to V-1, and an 2D vector/array which represents the edges:

Each entry in** edges[i] is of the form [u, v, weight]**, where:

**u, v **→ represents the vertex having undirected edge between them
weight → the weight of the edge between u and v

Given a source node S. Find the shortest distance of all the vertex from the source vertex S. Return a list of integers denoting **shortest distance **between each node and source vertex S. If a vertex is not reachable from source then its distance will be 109.

Input: V = 2, edges = [[0,1,9]] , S=0 Output: [0, 9] **Explanation: ** The shortest distance from node 0(source) to node 0 is 0 and the shortest distance from node 0 to node 1 is 9.

Input: V = 3, edges = [[0, 1, 1], [0, 2, 6], [1, 2, 3]] , S=2 Output: [4, 3, 0] **Explanation: ** For node 0, the shortest path is 2->1->0 (distance=4) For node 1, the shortest path is 2->1 (distance=3)

Input: V=4, edges = [[0,1,1],[0,3,2],[1,2,4],[2,3,3]] , S=0

1 ≤ V ≤ 10000
0 ≤ edges[i][j] ≤ 10000
1 ≤ edges.size() ≤ [ (V*(V - 1)) / 2 ]
0 ≤ S < V

cpp

class Solution{
public:
    vector<int> dijkstra(int V, vector<vector<int>> edges, int S) {

    }
};

java

class Solution
{
    public  int[] dijkstra(int V, ArrayList<ArrayList<Integer>> edges, int S)
    {
       
    }
}

python

class Solution:
    def dijkstra(self, V, edges, S):

javascript

class Solution {
    dijkstra(V, edges, S) {
  
    }
}

csharp

public class Solution
{
    public int[] Dijkstra(int V, List<List<int>> edges, int S)
    {
  
    }
}

func dijkstra(V int, edges [][]int, S int) []int {
	
}

Stuck? Show a way to structure it+

01Build an adjacency list and initialize every distance to infinity except the source.
02Use a min-heap of [distance, vertex] pairs, beginning with [0, source].
03Ignore stale heap entries and relax every outgoing edge from the current vertex.
04Return the finalized distances, mapping unreachable vertices to the required sentinel.

Reference answer

Dijkstra's algorithm applies when all edge weights are non-negative. Build an adjacency list for the undirected graph. Initialize dist[source] = 0, every other distance to infinity, and push (0, source) into a min-heap.

Repeatedly pop the pair with the smallest tentative distance. If the popped distance differs from dist[node], it is a stale entry created before a better route was discovered, so skip it. Otherwise, for every edge (node, neighbor, weight), compute candidate = dist[node] + weight. If that is smaller than dist[neighbor], update the distance and push the new pair. There is no need to remove the older heap entry because the stale-entry check handles it safely.

When the heap is empty, all reachable shortest distances are final. Convert remaining infinity values to the problem's 10^9 sentinel. With a binary heap, time is O((V + E) log V) and space is O(V + E). If negative edges are allowed, use Bellman-Ford or another appropriate algorithm instead.

Then expect these follow-ups

What changes if some edges can have negative weights?
Tests: algorithm selection
How would you reconstruct one shortest path, not just its distance?
Tests: path reconstruction

Hiring now

Linkedin has 196 open roles right now

Also hiring: Google

landed applies to roles like these for you, on each company’s own site, with answers written for the role.

Get 5x interviews10 free auto-applies. No card.

Software Engineer - Systems and Infrastructure
Mountain View, CA, United States
Staff Software Engineer
Mountain View, CA, United States
Staff Software Engineer, Systems Infrastructure
Bengaluru, KA, India

Or practice this question first

Next question