Dijkstra Algorithm (Find the Shortest Path) in C#

Dijkstra's Algorithm is one of the most popular graph algorithms used to find the shortest path between nodes in a weighted graph. It calculates the minimum distance from a starting node to all other nodes while ensuring that the shortest path found is optimal.

The algorithm was developed by Dutch computer scientist Edsger W. Dijkstra in 1956 and was formally published in 1959. Today, it remains one of the most widely used algorithms in computer science, networking, transportation systems, and route optimization software.

Key Characteristics:

Works with weighted graphs.
Requires non-negative edge weights.
Guarantees the shortest path.
Efficient when combined with priority queues.

How Does Dijkstra's Algorithm Work?

The algorithm starts from a source node and repeatedly selects the node with the smallest known distance. It then updates the distances of neighboring nodes if a shorter path is found through the current node.

Steps:

Assign distance 0 to the starting node.
Assign infinity to all other nodes.
Select the node with the smallest distance.
Update distances of neighboring nodes.
Mark the current node as visited.
Repeat until all nodes are processed.

Real-World Applications

GPS navigation systems.
Google Maps route calculations.
Network routing protocols.
Logistics and delivery optimization.
Game AI pathfinding.
Transportation and railway systems.

Graph Example

Consider the following graph:

From	To	Cost
A	B	4
A	C	2
B	D	5
C	D	8
C	E	10
D	E	2

If we start from node A, the shortest path to node E is:

A → B → D → E with a total cost of 11.

C# Dijkstra Algorithm Implementation

Complete Example

using System;
using System.Collections.Generic;

class Program
{
static Dictionary<string, List<(string neighbor, int cost)>> graph =
new Dictionary<string, List<(string, int)>>
{
{ "A", new List<(string,int)> { ("B",4), ("C",2) } },
{ "B", new List<(string,int)> { ("D",5) } },
{ "C", new List<(string,int)> { ("D",8), ("E",10) } },
{ "D", new List<(string,int)> { ("E",2) } },
{ "E", new List<(string,int)>() }
};

static Dictionary<string, int> Dijkstra(string start)
{
    var distances = new Dictionary<string, int>();
    var priorityQueue = new PriorityQueue<string, int>();

    foreach (var node in graph.Keys)
    {
      distances[node] = int.MaxValue;
    }

    distances[start] = 0;
    priorityQueue.Enqueue(start, 0);

    while (priorityQueue.Count > 0)
    {
      priorityQueue.TryDequeue(out string current, out int currentDistance);

      foreach (var (neighbor, cost) in graph[current])
      {
      int newDistance = currentDistance + cost;

      if (newDistance < distances[neighbor])
      {
      distances[neighbor] = newDistance;
      priorityQueue.Enqueue(neighbor, newDistance);
      }
      }
    }

    return distances;
}

static void Main()
{
    var result = Dijkstra("A");

    foreach (var item in result)
    {
      Console.WriteLine($"{item.Key} : {item.Value}");
    }
}
}

Example Output

A : 0
B : 4
C : 2
D : 9
E : 11

Time Complexity

Implementation	Time Complexity
Array / Matrix	O(V²)
Priority Queue (Heap)	O((V + E) log V)

Where:

V = Number of vertices (nodes)
E = Number of edges (connections)

Advantages of Dijkstra's Algorithm

Guaranteed shortest path for non-negative weights.
Easy to implement.
Highly efficient with priority queues.
Widely used in industry applications.

Limitations

Does not support negative edge weights.
Can become expensive for extremely large graphs.
Not always the fastest choice for specific pathfinding scenarios.

Alternative Shortest Path Algorithms

Algorithm	Supports Negative Weights	Main Use Case
Bellman-Ford	Yes	Graphs with negative edges
A*	No	Game development and navigation
Floyd-Warshall	Yes	All-pairs shortest paths
BFS	Only unweighted graphs	Simple shortest path searches

Dijkstra vs A*

Dijkstra explores all possible directions equally until it finds the shortest path. A* improves performance by using a heuristic function that estimates the distance to the destination. Because of this, A* is often preferred in game development and real-time navigation systems.

When Should You Use Dijkstra's Algorithm?

Finding shortest routes between cities.
Network packet routing.
Supply chain optimization.
Map and navigation applications.
Graph-based analytics systems.

Conclusion

Dijkstra's Algorithm remains one of the most important shortest-path algorithms in computer science. Despite being introduced more than six decades ago, it is still heavily used in modern software systems, navigation platforms, network infrastructures, and optimization engines. For C# developers working with graph data structures, understanding Dijkstra's Algorithm provides a strong foundation for solving real-world routing and pathfinding problems efficiently.