Djikstra algorithm for C#
using System; | |
using System.Collections.Generic; | |
using System.Linq; | |
using System.Text; | |
// Adapted from JavaScript example in The Imposter's Hanbook by Rob Conery | |
// Doesn't support negative edges! | |
namespace Djikstra | |
{ | |
class Path | |
{ | |
public string Name; | |
public int Cost; | |
public bool Visited; | |
public Path(string name, int cost, bool visited) | |
{ | |
Name = name; | |
Cost = cost; | |
Visited = visited; | |
} | |
} | |
class MemoTable | |
{ | |
private List<Path> Table; | |
public Path S; | |
public MemoTable(string[] vertices) | |
{ | |
S = new Path("S", 0, false); | |
Table = new List<Path>() {S}; | |
foreach (var vertex in vertices) | |
{ | |
Table.Add(new Path(vertex, int.MaxValue, false)); | |
} | |
} | |
private List<Path> GetCandidateVertices() | |
{ | |
return Table.Where(x => !x.Visited).ToList(); | |
} | |
public Path NextVertex() | |
{ | |
List<Path> candidates = GetCandidateVertices(); | |
if (candidates.Any()) | |
{ | |
return candidates.OrderBy(x => x.Cost).First(); | |
} | |
return null; | |
} | |
private Path GetEntry(string vertex) => Table.First(x => x.Name == vertex); | |
private void SetCurrentCost(string vertex, int cost) | |
{ | |
GetEntry(vertex).Cost = cost; | |
} | |
private void SetAsVisited(string vertex) | |
{ | |
GetEntry(vertex).Visited = true; | |
} | |
private int GetCost(string vertex) | |
{ | |
return GetEntry(vertex).Cost; | |
} | |
public void Evaluate(List<GraphItem> graph, Path vertex) | |
{ | |
GraphItem[] edges = graph.Where(x => x.From == vertex.Name).ToArray(); | |
foreach (var edge in edges) | |
{ | |
int currentVertexCost = GetCost(edge.From); | |
int toVertexCost = GetCost(edge.To); | |
int tentativeCost = currentVertexCost == int.MaxValue ? int.MaxValue : currentVertexCost + edge.Cost; | |
if (tentativeCost < toVertexCost) | |
SetCurrentCost(edge.To, tentativeCost); | |
} | |
SetAsVisited(vertex.Name); | |
Path next = NextVertex(); | |
if (next != null) | |
Evaluate(graph, next); | |
} | |
public override string ToString() | |
{ | |
StringBuilder buffer = new StringBuilder(); | |
foreach (var element in Table) | |
{ | |
buffer.AppendLine($"name: {element.Name}, cost: {element.Cost}, visited: {element.Visited}"); | |
} | |
return buffer.ToString(); | |
} | |
} | |
class GraphItem | |
{ | |
public string From; | |
public string To; | |
public int Cost; | |
public GraphItem(string from, string to, int cost) | |
{ | |
From = from; | |
To = to; | |
Cost = cost; | |
} | |
} | |
class Program | |
{ | |
static string[] vertices = { "A", "B", "C", "D", "E" }; | |
static List<GraphItem> graph = new List<GraphItem>() | |
{ | |
new GraphItem("S", "A", 4), | |
new GraphItem("S", "E", 2), | |
new GraphItem("A", "D", 3), | |
new GraphItem("A", "C", 6), | |
new GraphItem("A", "B", 5), | |
new GraphItem("B", "A", 3), | |
new GraphItem("C", "B", 1), | |
new GraphItem("D", "C", 3), | |
new GraphItem("D", "A", 1), | |
new GraphItem("E", "D", 1) | |
}; | |
static void Main() | |
{ | |
MemoTable memo = new MemoTable(vertices); | |
memo.Evaluate(graph, memo.S); | |
Console.WriteLine(memo.ToString()); | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment