 ## Dijkstra's Algorithm - Find Shortest Path

A very interesting algorithm that uses greedy approach to find the shortest path to the end node.
Imagine a connected pathways that takes different time to traverse as shown in the diagram below. ```public class Node
{
public string Name { get; set; }
public int Cost { get; set; }
public string From { get; set; }
public bool Visited { get; set; }
public Dictionary&lt;int, Node&gt; Neighbors { get; set; }
}

public class Graph
{
private List NodeGraph { get; }

public Graph(List graph)
{
NodeGraph = graph;
}

public List ShortestPath()
{
//Starting from the first node.
var start = NodeGraph;

//if picked, the item is visited
while (start != null &amp;&amp; start.Visited == false)
{
start.Visited = true;

//if the cost is lower when visitng from another node, replace the cost value
foreach (var neighbor in start.Neighbors)
{
var cost = start.Cost + neighbor.Key;
if (neighbor.Value.Cost > cost &amp;&amp; !neighbor.Value.Visited)
{
neighbor.Value.Cost = cost;
neighbor.Value.From = start.Name;
}
}

//find the minimum cost node for the next iteration
Node next = null;
foreach (var neighbor in start.Neighbors)
{
//start from first neighbor and replace it by the
//lower cost neighbor that is not already visited
if (next == null) next = neighbor.Value;
if (neighbor.Value.Visited != true &amp;&amp; next.Cost >= neighbor.Value.Cost)
next = neighbor.Value;
}

start = next;
}

return NodeGraph;
}
}

static void Main(string[] args)
{
Node _aNode, _bNode, _cNode, _dNode, _eNode, _fNode, _gNode, _hNode;

_aNode = new Node { Name = "A", Cost = 0, Visited = false };
_bNode = new Node { Name = "B", Cost = int.MaxValue, Visited = false };
_cNode = new Node { Name = "C", Cost = int.MaxValue, Visited = false };
_dNode = new Node { Name = "D", Cost = int.MaxValue, Visited = false };
_eNode = new Node { Name = "E", Cost = int.MaxValue, Visited = false };
_fNode = new Node { Name = "F", Cost = int.MaxValue, Visited = false };
_gNode = new Node { Name = "G", Cost = int.MaxValue, Visited = false };
_hNode = new Node { Name = "H", Cost = int.MaxValue, Visited = false };

//A can go to to D, B, G
//B can go to F
//C can go to D, F, H
//D can go to G
//E can go to B, G
//F can go to C, D
//G can go to A
//H can go to none
_aNode.Neighbors = new Dictionary<int, Node>() { { 20, _bNode }, { 80, _dNode }, { 90, _gNode } };
_bNode.Neighbors = new Dictionary<int, Node>() { { 10, _fNode } };
_cNode.Neighbors = new Dictionary<int, Node>() { { 10, _dNode }, { 50, _fNode }, { 20, _hNode } };
_dNode.Neighbors = new Dictionary<int, Node>() { { 20, _gNode } };
_eNode.Neighbors = new Dictionary<int, Node>() { { 50, _bNode }, { 30, _gNode } };
_fNode.Neighbors = new Dictionary<int, Node>() { { 10, _cNode }, { 40, _dNode } };
_gNode.Neighbors = new Dictionary<int, Node>() { { 20, _aNode } };
_hNode.Neighbors = new Dictionary<int, Node>();

var graph = new List() { _aNode, _bNode, _cNode, _dNode, _eNode, _fNode, _gNode, _hNode };

//initialize graph and call Dijkstra's Algorithm
var sp = new Graph(graph);
graph = sp.ShortestPath();

//print the graph with shortest path
foreach (var node in graph)
{
Console.WriteLine("Node = " + node.Name + ", Cost = " + node.Cost + " from " + node.From);
}

}```

Posted in:  Algorithm

## Heap Sort Algorithm

Heap sort is a common sorting algorithm, but useful in case of hierarchical or tree kind of data structures.
```public class HeapSort
{

public HeapSort(List<int> heapList, int heapsize)
{
this._heapsize = heapsize;
this._heapList = heapList;
}

private void Heapify(int i, int n)
{
var iPosition = _heapList[i];
var iChange = 2 * i;
while (iChange <= n)
{
if (iChange < n && _heapList[iChange] < _heapList[iChange + 1])
{
iChange++;
}
if (iPosition >= _heapList[iChange])
{
break;
}
_heapList[iChange / 2] = _heapList[iChange];
iChange *= 2;
}
_heapList[iChange / 2] = iPosition;
}

public void Sort()
{
for (var i = _heapsize / 2; i >= 0; i--)
{
Heapify(i, _heapsize - 1);
}

for (var i = _heapsize - 2; i >= 0; i--)
{
var iValue = _heapList[i + 1];
_heapList[i + 1] = _heapList;
_heapList = iValue;
Heapify(0, i);
}
}

public string PrintList()
{
var myValue = "";
for (int i = 0; i < _heapsize; i++)
{
myValue += _heapList[i] + " ";
}
return myValue;
}
}```

Posted in:  Algorithm