source: branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithm.cs @ 8308

using System.Collections.Generic;
using HeuristicLab.Problems.RoutePlanning.Graph;
namespace HeuristicLab.Algorithms.GraphRouting {
  public class DijkstraAlgorithm : IRouter {
    private Graph graph;

    public DijkstraAlgorithm(Graph graph) {
      this.graph = graph;
    }

    #region IRouter Members

    public long[] Calculate(long sourceNodeId, long targetNodeId) {
      HashSet<long> visitedNodes = new HashSet<long>();        // visited
      HashSet<long> unvisitedNodes = new HashSet<long>();      // unvisited
      Dictionary<long, long> distances = new Dictionary<long, long>();
      Dictionary<long, long> predecessors = new Dictionary<long, long>();

      long currentNode;
      Dictionary<long, float> currentNeighbors = new Dictionary<long, float>();
      List<long> resultRoute = new List<long>();

      if (sourceNodeId == targetNodeId) {
        resultRoute.Add(sourceNodeId);
        return resultRoute.ToArray();
      }

      distances.Add(sourceNodeId, 0);
      unvisitedNodes.Add(sourceNodeId);

      currentNode = sourceNodeId;
      currentNeighbors = graph.GetNeighbors(currentNode);

      while (unvisitedNodes.Count > 0) {
        //Vertex node = getMinimum(unSettledNodes);
        //settledNodes.add(node);
        //unSettledNodes.remove(node);
        //findMinimalDistances(node);

        //currentNode = GetMinimum(unvisitedNodes);
        visitedNodes.Add(currentNode);
        unvisitedNodes.Remove(currentNode);

        if (currentNode == targetNodeId) {
          break;
        }

        currentNeighbors = graph.GetNeighbors(currentNode);

      }

      if (currentNode != targetNodeId) {
        // target was not found
        // maybe throw exception
      }
      return resultRoute.ToArray();
    }

    #endregion

    //private long GetMinimum(HashSet<long> nodeIds) {
    //  long minimum = -1;
    //  foreach (long id in nodeIds) {
    //    if (minimum == -1) minimum = id;
    //    else {
    //      if (GetDistance(id) < GetDistance(minimum)) {
    //        minimum = id;
    //      }
    //    }
    //  }
    //}
  }
}