using System;
using System.Collections.Generic;
using System.Linq;
public static class DijkstraWithoutQueue
{
public static List<int> DijkstraAlgorithm(int[,] graph, int sourceNode, int destinationNode)
{
var n = graph.GetLength(0);
var distance = new int[n];
for (int i = 0; i < n; i++)
{
distance[i] = int.MaxValue;
}
distance[sourceNode] = 0;
var used = new bool[n];
var previous = new int?[n];
while (true)
{
var minDistance = int.MaxValue;
var minNode = 0;
for (int i = 0; i < n; i++)
{
if (!used[i] && minDistance > distance[i])
{
minDistance = distance[i];
minNode = i;
}
}
if (minDistance == int.MaxValue)
{
break;
}
used[minNode] = true;
for (int i = 0; i < n; i++)
{
if (graph[minNode, i] > 0)
{
var shortestToMinNode = distance[minNode];
var distanceToNextNode = graph[minNode, i];
var totalDistance = shortestToMinNode + distanceToNextNode;
if (totalDistance < distance[i])
{
distance[i] = totalDistance;
previous[i] = minNode;
}
}
}
}
if (distance[destinationNode] == int.MaxValue)
{
return null;
}
var path = new LinkedList<int>();
int? currentNode = destinationNode;
while (currentNode != null)
{
path.AddFirst(currentNode.Value);
currentNode = previous[currentNode.Value];
}
return path.ToList();
}
public static void Main()
{
var graph = new[,]
{
// 0 1 2 3 4 5 6 7 8 9 10 11
{ 0, 0, 0, 0, 0, 0, 10, 0, 12, 0, 0, 0 }, // 0
{ 0, 0, 0, 0, 20, 0, 0, 26, 0, 5, 0, 6 }, // 1
{ 0, 0, 0, 0, 0, 0, 0, 15, 14, 0, 0, 9 }, // 2
{ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 0 }, // 3
{ 0, 20, 0, 0, 0, 5, 17, 0, 0, 0, 0, 11 }, // 4
{ 0, 0, 0, 0, 5, 0, 6, 0, 3, 0, 0, 33 }, // 5
{10, 0, 0, 0, 17, 6, 0, 0, 0, 0, 0, 0 }, // 6
{ 0, 26, 15, 0, 0, 0, 0, 0, 0, 3, 0, 20 }, // 7
{12, 0, 14, 0, 0, 3, 0, 0, 0, 0, 0, 0 }, // 8
{ 0, 5, 0, 0, 0, 0, 0, 3, 0, 0, 0, 0 }, // 9
{ 0, 0, 0, 7, 0, 0, 0, 0, 0, 0, 0, 0 }, // 10
{ 0, 6, 9, 0, 11, 33, 0, 20, 0, 0, 0, 0 }, // 11
};
PrintPath(graph, 0, 9);
PrintPath(graph, 0, 2);
PrintPath(graph, 0, 10);
PrintPath(graph, 0, 11);
PrintPath(graph, 0, 1);
}
public static void PrintPath(int[,] graph, int sourceNode, int destinationNode)
{
Console.Write(
"Shortest path [{0} -> {1}]: ",
sourceNode,
destinationNode);
var path = DijkstraWithoutQueue.DijkstraAlgorithm(graph, sourceNode, destinationNode);
if (path == null)
{
Console.WriteLine("no path");
}
else
{
int pathLength = 0;
for (int i = 0; i < path.Count - 1; i++)
{
pathLength += graph[path[i], path[i + 1]];
}
var formattedPath = string.Join("->", path);
Console.WriteLine("{0} (length {1})", formattedPath, pathLength);
}
}
}
Tag: Simple
How to generate Combinations without repetition recursively in C#
// 1: [0, 1]
// 2: [0, 2]
// 3: [0, 3]
// 4: [1, 2]
// 5: [1, 3]
// 6: [2, 3]
using System;
public static class CombinationsNoRep
{
private static int numberofCombos;
private static int n;
private static int k;
private static int[] storageArr;
public static void Main()
{
n = 4;
k = 2;
storageArr = new int[k];
GenCombinationsNoRep();
}
private static void GenCombinationsNoRep(int index = 0, int element = 0)
{
if (index >= storageArr.Length)
{
PrintCombo();
return;
}
for (int i = element; i < n; i++)
{
storageArr[index] = i;
GenCombinationsNoRep(index + 1, i + 1);
}
}
private static void PrintCombo()
{
Console.WriteLine(
"{0,3}: [{1}]",
++numberofCombos,
string.Join(", ", storageArr));
}
}
Simple implementation of generic BINARY TREE in C#
using System;
public class BinaryTree
{
public BinaryTree(
T value,
BinaryTree leftNode = null,
BinaryTree rightNode = null)
{
this.Value = value;
this.LeftNode = leftNode;
this.RightNode = rightNode;
}
public T Value { get; private set; }
public BinaryTree LeftNode { get; private set; }
public BinaryTree RightNode { get; private set; }
public void EachPreOrder(Action action)
{
action(this.Value);
if (this.LeftNode != null)
{
this.LeftNode.EachPreOrder(action);
}
if (this.RightNode != null)
{
this.RightNode.EachPreOrder(action);
}
}
public void EachInOrder(Action action)
{
if (this.LeftNode != null)
{
this.LeftNode.EachPreOrder(action);
}
action(this.Value);
if (this.RightNode != null)
{
this.RightNode.EachPreOrder(action);
}
}
public void EachPostOrder(Action action)
{
if (this.LeftNode != null)
{
this.LeftNode.EachPreOrder(action);
}
if (this.RightNode != null)
{
this.RightNode.EachPreOrder(action);
}
action(this.Value);
}
}
Simple implementation of generic TREE in C#
using System;
using System.Collections.Generic;
public class Tree<T>
{
public Tree(
T value,
params Tree<T>[] children)
{
this.Value = value;
this.Children = new List<Tree<T>>();
foreach (var child in children)
{
this.Children.Add(child);
}
}
public T Value { get; private set; }
public ICollection<Tree<T>> Children { get; private set; }
public void EachTree(Action<T> action)
{
action(this.Value);
foreach (var child in this.Children)
{
child.EachTree(action);
}
}
public void PrintTree(int indent = 0)
{
Console.WriteLine(new string(' ', indent * 2) + this.Value);
indent++;
foreach (var child in this.Children)
{
child.PrintTree(indent);
}
}
}
Simple static implementation of generic QUEUE in C#
public class CircularQueue<T>
{
private const int InitialCapacity = 16;
private T[] storage;
private int capacity;
private int startIndex;
private int endIndex;
public CircularQueue(int capacity = InitialCapacity)
{
this.Capacity = capacity;
this.storage = new T[this.Capacity];
}
public int Count { get; private set; }
private int Capacity
{
get
{
return this.capacity;
}
set
{
if (value <= 0)
{
throw new ArgumentOutOfRangeException(
nameof(value),
"Queue capacity should be a positive integer");
}
this.capacity = value;
}
}
public void Enqueue(T element)
{
if (this.GrowNeeded())
{
this.Grow();
}
this.storage[this.endIndex] = element;
this.endIndex = (this.endIndex + 1) % this.Capacity;
this.Count++;
}
public T Dequeue()
{
if (this.Count <= 0)
{
throw new InvalidOperationException("Queue is empty.");
}
var element = this.storage[this.startIndex];
this.storage[this.startIndex] = default(T);
this.startIndex = (this.startIndex + 1) % this.Capacity;
this.Count--;
return element;
}
public T[] ToArray()
{
var resultArray = new T[this.Count];
this.ResizeArrayStorage(resultArray);
return resultArray;
}
private bool GrowNeeded()
{
var result = this.Count >= this.Capacity;
return result;
}
private void Grow()
{
var newStorage = new T[this.Capacity * 2];
this.ResizeArrayStorage(newStorage);
this.startIndex = 0;
this.endIndex = this.Capacity;
this.Capacity *= 2;
this.storage = newStorage;
}
private void ResizeArrayStorage(T[] array)
{
for (int i = 0; i < this.Count; i++)
{
var currentIndex = (this.startIndex + i) % this.Capacity;
array[i] = this.storage[currentIndex];
}
}
}