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[0]; //if picked, the item is visited while (start != null &amp;&amp; start.Visited == false) { start.Visited = true; //adjust the cost of visiting neighbors if not already visited //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) { //adjust cost and remember predecessor 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; } //finally return the adjusted node 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); } Console.ReadLine(); }

 
  Posted in:  Algorithm



Heap sort is a common sorting algorithm, but useful in case of hierarchical or tree kind of data structures.
public class HeapSort { private readonly List<int> _heapList; private readonly int _heapsize; 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[0]; _heapList[0] = iValue; Heapify(0, i); } } public string PrintList() { var myValue = ""; for (int i = 0; i < _heapsize; i++) { myValue += _heapList[i] + " "; } return myValue; } }

 
  Posted in:  Algorithm