Permalink
Find file
Fetching contributors…
Cannot retrieve contributors at this time
80 lines (64 sloc) 2.56 KB
using Core.Collections.Extensions.Heap;
using System;
using System.Collections.Generic;
namespace Core.Algorithms.Pathfinding
{
// For a good conceptual overview of Dijkstra's shortest path algorithm,
// visit: http://www.eoinbailey.com/content/dijkstras-algorithm-illustrated-explanation
public class Dijkstra
{
public static List<Point> ShortestPath(Point src, Point dest)
{
// keep track of visited nodes in the graph
var visited = new HashSet<Point>();
visited.Add(src);
// process all nodes in order of their shortest distance from src
var minHeap = new List<IComparable>();
// start w/ src node, then fan out by shortest distances
foreach (var key in src.Neighbors.Keys)
{
minHeap.HeapPush(new ShortestPathEntry()
{
Point = key,
Length = src.Neighbors[key].Length,
Path = new List<Point>() { src, key }
});
}
while (minHeap.Count > 0)
{
var point = minHeap.HeapPop() as ShortestPathEntry;
if (!visited.Add(point.Point)) { continue; }
if (point.Point == dest) { return point.Path; }
foreach (var key in point.Point.Neighbors.Keys)
{
if (visited.Contains(key)) { continue; }
var path = new List<Point>();
path.AddRange(point.Path);
path.Add(key);
int currentLength = point.Length + point.Point.Neighbors[key].Length;
minHeap.HeapPush(new ShortestPathEntry()
{
Point = key,
Length = currentLength,
Path = path
});
}
}
return new List<Point>(); // won't happen if destination is reached
}
private class ShortestPathEntry : IComparable, IComparable<ShortestPathEntry>
{
public Point Point { get; set; }
public int Length { get; set; }
public List<Point> Path { get; set; }
public int CompareTo(object other)
{
return CompareTo((ShortestPathEntry)other);
}
public int CompareTo(ShortestPathEntry other)
{
return this.Length - other.Length;
}
}
}
}