Featured Image of Edsger Wybe Dijkstra from Wikipedia, used under CC BY 3.0.

I've spent about 3 days trying to implement Dijkstra's algorithm after watching a YouTube video.

I've implemented three times (once a day) but on the 3rd day, I finally succeeded.

This entry is neither going to be about what Dijkstra's algorithm is nor how the implementation works. I will just talk about steps I took to implement it and post the full source link on the bottom.

Here is how I spent each day.

Day 1

I used pseudocode on Wikipedia page and some other algorithms I found elsewhere. I failed splendidly because I didn't understand how the algorithm worked behind the scenes.

Here is the failed implementation.

1public List<T> GetPathBetween(Node<T> fromNode, Node<T> toNode)2{3    List<T> path = new List<T>();4    var dist = new Dictionary<Node<T>, int>();5    // unvisited nodes6    var fringe = new List<Node<T>>();7
8    foreach (KeyValuePair<Node<T>, Edge<T>\[\]> vertext in \_vertices)9    {10        // Unknown distance from source to v11        dist\[vertext.Key\] = int.MaxValue;   // int.MaxValue => infinity12        foreach (Edge<T> edge in vertext.Value)13        {14            dist\[edge.Node\] = int.MaxValue;15        }16        // All nodes initially in Q (unvisited nodes)17        fringe.Add(vertext.Key);18    }19
20    // Distance from source to source21    //KeyValuePair<Node<T>, int> first = dist.FirstOrDefault(pair => pair.Value == fromNode.Value);22    KeyValuePair<Node<T>, int> first = dist.FirstOrDefault(pair => pair.Key.Value.Equals(fromNode.Value));23    dist\[first.Key\] = 0;    // distance from itself is 024
25    while (fringe.Count > 0)26    {27        // shortest path28        var processed = dist.Where(pair => !path.Contains(pair.Key.Value)).ToList();29        Node<T> m = processed.FirstOrDefault(pair => pair.Value == processed.Min(p => p.Value)).Key;30        int mDist = dist\[m\];31        fringe.Remove(m);32
33        if (!\_vertices.ContainsKey(m))34        {35            dist.Remove(m);36            continue;37        }38
39        foreach (Edge<T> w in \_vertices\[m\])40        {41            if (dist\[w.Node\] == int.MaxValue)42            {43                dist\[w.Node\] = mDist + (mDist + w.Weight);44                fringe.Add(w.Node);45            }46            else47            {48                dist\[w.Node\] = Math.Min(dist\[w.Node\], mDist + (mDist + w.Weight));49            }50        }51        path.Add(m.Value);52    }53
54    return path;55}

It's basically a hodgepodge of a mess (the last implementation looks ugly as well by the way) and doesn't work at all. I knew that I was lacking knowledge on how the algorithm worked.

Day 2

After understanding how the algorithm works was important, I found a great video on YouTube by Sesh Venugopal and watched it before implementing another version.

The video explains visually how the algorithm works. The video also explains its own version of the algorithm. I decided to use the algorithm in the video to implement for the second time.

But I failed beautifully again because I couldn't get the Wikipedia and other versions of algorithms out of my head.

Here is the 2nd failed attempt.

1public List<Node<T>> GetPathBetween2(Node<T> fromNode, Node<T> toNode)2{3var s = \_vertices;4var dist = new Dictionary<Node<T>, int>();5var prev = new Dictionary<Node<T>, T>();6var Q = new List<Node<T>>();7var processed = new List<Node<T>>();8
9    // Initial10    KeyValuePair<Node<T>, Edge<T>\[\]> first = s.First(pair => pair.Key.Value.Equals(fromNode.Value));11    foreach (var v in \_vertices.Where(pair => !pair.Key.Value.Equals(first.Key.Value)))12    {13        foreach (Edge<T> edge in v.Value)14        {15            dist\[edge.Node\] = int.MaxValue; // inifinity16            Q.Add(edge.Node);17        }18    }19
20    foreach (Edge<T> edge in first.Value)21    {22        dist\[edge.Node\] = edge.Weight;23        Q.Add(edge.Node);24    }25
26    dist\[first.Key\] = 0;27    prev\[first.Key\] = first.Key.Value;28    Q.Add(first.Key);29
30    while (Q.Count > 0)31    {32        var notProcessed = dist.Where(pair => !processed.Contains(pair.Key)).ToList();33        if (notProcessed.Count == 0) break;34
35        // Remove the minimum distance vertex, say m, from the fringe36        // (it is done, the shortest path to it has been found)37        Node<T> u = Q.First(node =>38        {39            var min = notProcessed.Min(pair => pair.Value);40            return dist\[node\].Equals(min);41        });42        Q.Remove(u);43
44        if (\_vertices.ContainsKey(u))45        {46            foreach (Edge<T> v in \_vertices\[u\])47            {48                var alt = dist\[u\] + v.Weight;49                if (alt < dist\[v.Node\])50                {51                    dist\[v.Node\] = alt;52                    if (!prev.Values.Contains(u.Value))53                        prev\[v.Node\] = u.Value;54                }55            }56        }57
58        if (u.Value.Equals(toNode.Value))59        {60            prev\[toNode\] = toNode.Value;61            return new List<Node<T>>(prev.Distinct().Select(pair => new Node<T>(pair.Value)));62        }63
64        processed.Add(u);65    }66
67    return prev.Select(pair => pair.Key).ToList();68
69}

Day 3

I read Wikipedia pseudocode again. I was armed with the knowledge of how the algorithm worked after watching the video, I decided to read Wikipedia algorithm and give it one more try.

After some struggle here and there, I've finally completed the implementation.

It's kind of funny that, after watching it work, I felt ecstatic and felt a jolt in my head. "Ah, this is why I decided to learn to program" was my first thought after realizing what happened.

Here is the 3rd working implementation.

1public List<Node<T>> GetPathBetween3(Node<T> fromNode, Node<T> toNode)2{3var dist = new Dictionary<Node<T>, int>();4var prev = new Dictionary<Node<T>, Node<T>>();5var Q = new HashSet<Node<T>>();6
7    foreach (KeyValuePair<Node<T>, Edge<T>\[\]> v in \_vertices)8    {9        foreach (Edge<T> edge in v.Value)10        {11            // Unknown distance from source to v12            dist\[edge.Node\] = int.MaxValue;13            // Previous node in optimal path from source14            prev\[edge.Node\] = null;15            Q.Add(edge.Node);16        }17    }18    // Distance from source to source19    dist\[fromNode\] = 0;20    Q.Add(fromNode);21
22    // while Q is not empty:23    while (Q.Count > 0)24    {25        // Node with the Least distance will be selected26        // Note that order is not guaranteed.27        Node<T> u = (from distance in dist28                        where Q.Contains(distance.Key) && distance.Value == dist.Where(pair => Q.Contains(pair.Key)).Min(pair => pair.Value)29                        select distance.Key).FirstOrDefault();30
31        if (u.Value.Equals(toNode.Value))32        {33            var S = new Stack<Node<T>>();34            while (prev.ContainsKey(u))35            {36                S.Push(u);37                u = prev\[u\];38            }39            S.Push(u);40            return S.ToList();41        }42
43        Q.Remove(u);44        if (!\_vertices.ContainsKey(u)) continue;45
46        foreach (Edge<T> v in \_vertices\[u\])47        {48            var alt = dist\[u\] + v.Weight;49            if (alt < dist\[v.Node\])50            {51                dist\[v.Node\] = alt;52                prev\[v.Node\] = u;53            }54        }55
56    }57
58    return null;59
60}

It's by no means production ready, so copy/paste at your own risk. I'd never release this to production without heavy testing and refactoring first.

Here is the full source (including Main, Node, Graph implementations) on GitHub.

Also, check out Max Burstein's C# implementation on GitHub. I found Max's implementation much cleaner and easier to understand.

Conclusion

The journey was tough but was quite worth it. It has given me more confidence as a developer.