Find a weighted shortest path with Dijkstra
Find the shortest distance from a start vertex to a target in a graph with non-negative edge weights.
Course progress
Problem 80 of 100
Example → approach → runnable solution
Worked example
See the problem in action
Trace a concrete input through to the verified result.
Example input
start = 0; target = 4; weighted graph as shown in the solution
Expected output
7
What is happening?
The least-cost route is 0 -> 2 -> 1 -> 3 -> 4 with weights 1 + 2 + 1 + 3, totaling 7.
Solution strategy
Build the right mental model
Repeatedly settle the unvisited vertex with the smallest known distance, then relax each of its outgoing edges.
Core concepts
graphs · greedy algorithms
Complexity
Time O(V^2) with an adjacency matrix, space O(V).
Runnable solution
Learn from working code
Compare languages, copy the code, or open it in the compiler.
Complete C# solution for dijkstra-shortest-path
using System;
class Program
{
static int ShortestDistance(int[,] graph, int start, int target)
{
int vertices = graph.GetLength(0);
int[] distance = new int[vertices];
bool[] visited = new bool[vertices];
for (int i = 0; i < vertices; i++) distance[i] = int.MaxValue;
distance[start] = 0;
for (int step = 0; step < vertices; step++)
{
int current = -1;
for (int vertex = 0; vertex < vertices; vertex++)
if (!visited[vertex] && distance[vertex] != int.MaxValue &&
(current == -1 || distance[vertex] < distance[current])) current = vertex;
if (current == -1 || current == target) break;
visited[current] = true;
for (int neighbor = 0; neighbor < vertices; neighbor++)
if (graph[current, neighbor] > 0 && !visited[neighbor] &&
distance[current] <= int.MaxValue - graph[current, neighbor])
distance[neighbor] = Math.Min(distance[neighbor],
distance[current] + graph[current, neighbor]);
}
return distance[target] == int.MaxValue ? -1 : distance[target];
}
static void Main()
{
int[,] graph = {
{ 0, 4, 1, 0, 0 }, { 4, 0, 2, 1, 0 },
{ 1, 2, 0, 5, 0 }, { 0, 1, 5, 0, 3 },
{ 0, 0, 0, 3, 0 }
};
Console.WriteLine(ShortestDistance(graph, 0, 4));
}
}Knowledge check
Questions students often ask
What is the main idea behind find a weighted shortest path with dijkstra?
Repeatedly settle the unvisited vertex with the smallest known distance, then relax each of its outgoing edges.
What is the time and space complexity of this solution?
Time O(V^2) with an adjacency matrix, space O(V).
Do all language tabs solve the same problem?
Yes. Every program uses the same example and produces the verified output shown on this page. The syntax and a few language-specific data structures differ.