LESSON 340 OF 347 · GRAPHS

Dijkstra's Algorithm in C#: Shortest Distances from Vertex 0

Practice Priority Queue, O((V+E) log V) Read the full explanation

Given a weighted undirected graph with n vertices (labeled 0 to n-1) and a list of edges where edges[i] = [u, v, weight], find the shortest distance from vertex 0 to every other vertex using Dijkstra's algorithm.

Return an array dist of length n where dist[i] is the shortest distance from vertex 0 to vertex i. All vertices are reachable.

Example

Input: n = 5, edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]]
Output: [0, 3, 1, 4, 7]
Explanation:
- 0 → 0: distance 0
- 0 → 2 → 1: distance 1 + 2 = 3
- 0 → 2: distance 1
- 0 → 2 → 1 → 3: distance 1 + 2 + 1 = 4
- 0 → 2 → 1 → 3 → 4: distance 1 + 2 + 1 + 3 = 7

Constraints

2 <= n <= 1000
1 <= edges.length <= 5000
0 <= u, v < n
1 <= weight <= 1000
The graph is connected.

STEP 1 OF 9

Guided

Ctrl + Enter to check

C# · GRAPHS

Dijkstra in C#, explained

Problem overview

Dijkstra(n, edges) receives a connected, undirected, weighted graph with vertices 0 to n - 1. Each edge is [u, v, weight] with a weight from 1 to 1000. It returns an array dist where dist[i] is the length of the cheapest path from vertex 0 to vertex i. A path's length is the sum of its edge weights.

For n = 5 and edges = [[0,1,4],[0,2,1],[2,1,2],[1,3,1],[2,3,5],[3,4,3]] the answer is [0, 3, 1, 4, 7]. Vertex 1 is cheaper to reach as 0 to 2 to 1, costing 1 + 2 = 3, than by the direct edge of weight 4.

Approach: always settle the closest unsettled vertex

With equal weights, plain BFS gives shortest paths. With varied weights it doesn't, because a path with fewer edges can cost more. Dijkstra's algorithm handles non-negative weights with a greedy rule: keep a best-known distance for every vertex, and repeatedly take the not-yet-finished vertex with the smallest known distance. Its distance is final, because any other route to it would have to pass through a vertex that is at least as far away, and weights can't be negative.

When a vertex is taken, relax its edges. For an edge to a neighbour v with weight w, if dist[u] + w is smaller than the current dist[v], record the better value.

The "take the smallest" step is a job for a priority queue. This lesson uses a plain List that is re-sorted on every iteration, which is simple and fast enough for at most 1000 vertices and 5000 edges. Rather than updating an existing entry when a shorter path appears, it adds a new entry and ignores outdated ones when they come out. This is called lazy deletion.

Step by step

Create adj, an array of n lists of int[], and give every slot a fresh list in a loop. A new array of reference types is filled with null.
For each edge, add {v, weight} to the list of u and {u, weight} to the list of v. The graph is undirected, so each edge is stored from both ends.
Create dist and fill it with int.MaxValue to mean "not reached", then set dist[0] = 0.
Create the working list pq and add the pair {0, 0}, the distance first, then the vertex. Putting the distance first makes sorting by distance easy.
Loop while pq.Count > 0.
Sort pq by distance, take the first pair as cur and remove it with RemoveAt(0). Read d and u. If d is greater than dist[u], a better entry for u was already processed, so skip this stale one.
Loop over the neighbours nb of u.
Read v and w. If dist[u] + w < dist[v], set dist[v] to that value and add {dist[v], v} to the list. Only improving paths are added, so the list doesn't fill with useless entries.
Return dist.

The solution in C#

class Solution {
    public int[] Dijkstra(int n, int[][] edges) {
        var adj = new List<int[]>[n];
        for (int i = 0; i < n; i++) {
            adj[i] = new List<int[]>();
        }
        foreach (int[] e in edges) {
            adj[e[0]].Add(new int[]{e[1], e[2]});
            adj[e[1]].Add(new int[]{e[0], e[2]});
        }
        int[] dist = new int[n];
        for (int i = 0; i < n; i++) {
            dist[i] = int.MaxValue;
        }
        dist[0] = 0;
        var pq = new List<int[]>();
        pq.Add(new int[]{0, 0});
        while (pq.Count > 0) {
            pq.Sort((a, b) => a[0] - b[0]);
            int[] cur = pq[0];
            pq.RemoveAt(0);
            int d = cur[0], u = cur[1];
            if (d > dist[u]) {
                continue;
            }
            foreach (int[] nb in adj[u]) {
                int v = nb[0], w = nb[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.Add(new int[]{dist[v], v});
                }
            }
        }
        return dist;
    }
}

Trace the example. The list starts as [(0, vertex 0)]. Taking vertex 0 sets dist[1] = 4 and dist[2] = 1. The smallest entry is now vertex 2 at distance 1. Its edges improve vertex 1 to 1 + 2 = 3 and set vertex 3 to 1 + 5 = 6. Next comes vertex 1 at distance 3, which improves vertex 3 to 4. The old entry for vertex 1 at distance 4 is still in the list. When it is taken, 4 > dist[1] (which is 3), so it is skipped. Vertex 3 at distance 4 then sets vertex 4 to 7, and the final array is [0, 3, 1, 4, 7].

Some C# details:

Array of lists. var adj = new List<int[]>[n]; allocates only the array, so each element is null until the loop assigns a list. Reading adj[i].Add(...) before that throws NullReferenceException.
No overflow. dist[u] + w is computed only for a vertex u that has been reached, so dist[u] is a real distance and the sum can't overflow the way int.MaxValue + w would. In C#, int arithmetic wraps silently by default, which would give a large negative number.
Sort with a lambda. a[0] - b[0] orders pairs by distance, smallest first. The subtraction is safe because the distances are small.
RemoveAt(0) removes the first element and shifts all the others down, which costs time proportional to the list's length.
A real priority queue. .NET has PriorityQueue<TElement, TPriority> (in System.Collections.Generic). With it, the main loop becomes while (pq.TryDequeue(out int u, out int d)), pq.Enqueue(v, dist[v]) adds an entry, and no sorting is needed.

Complexity

Let E be the number of edges. Every successful relaxation adds one entry, and there are at most 2E of those, since each edge is examined from both ends. With a binary-heap priority queue, the total time is O(E log V). This lesson's list sorts on every iteration, so each pass costs about O(P log P) for a list of P entries, and the total is higher. That is acceptable for the lesson's limits but not for large graphs.

Space: O(V + E) for the adjacency lists and the entries waiting in the queue.

Edge cases and common mistakes

Parallel edges. If two edges join the same vertices with different weights, relaxation keeps the cheaper one. With edges = [[0,1,7],[0,1,3]] the answer is [0, 3].
A direct edge that isn't the cheapest. With edges = [[1,0,5],[2,1,5],[0,2,20]] the answer is [0, 5, 10]. The direct edge to vertex 2 costs 20, and the route through vertex 1 costs only 10.
Forgetting the stale-entry check. The answer is still correct, since outdated entries can't improve anything. Without the check, you repeat work for no gain.
Adding each edge in one direction. The graph is undirected, so both endpoints need the edge, or some vertices are unreachable.
Negative weights. Dijkstra's algorithm assumes weights are never negative. The greedy claim "the smallest known distance is final" is false otherwise, and other algorithms such as Bellman-Ford are needed. This lesson guarantees weights from 1 to 1000.
Starting distances at 0. If dist keeps its default zeros, no relaxation ever succeeds. The sentinel must be larger than any real distance.

Testing

n = 5, the example's edges, gives [0, 3, 1, 4, 7].
n = 2, edges = [[0,1,7],[0,1,3]] gives [0, 3].
n = 3, edges = [[1,0,5],[2,1,5],[0,2,20]] gives [0, 5, 10].

Keep going with C#About 340 step-by-step lessons, from your first line of code to coding interviews. Free to start.

Start learning free