Free cookie consent management tool by TermsFeed Policy Generator

Changeset 8312


Ignore:
Timestamp:
07/20/12 11:19:43 (12 years ago)
Author:
spimming
Message:

#1894: worked on Dijkstra algorithm

File:
1 edited

Legend:

Unmodified
Added
Removed

  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/DijkstraAlgorithm.cs

    r8308 r8312  
    11
     2using System;
    23using System.Collections.Generic;
    34using HeuristicLab.Problems.RoutePlanning.Graph;
    … …  
    56  public class DijkstraAlgorithm : IRouter {
    67    private Graph graph;
     8
     9    private HashSet<long> visitedNodes;
     10    private HashSet<long> unvisitedNodes;
     11    private Dictionary<long, float> distances;
     12    private Dictionary<long, long> predecessors;
    713
    814    public DijkstraAlgorithm(Graph graph) {
    … …  
    1319
    1420    public long[] Calculate(long sourceNodeId, long targetNodeId) {
    15       HashSet<long> visitedNodes = new HashSet<long>();        // visited
    16       HashSet<long> unvisitedNodes = new HashSet<long>();      // unvisited
    17       Dictionary<long, long> distances = new Dictionary<long, long>();
    18       Dictionary<long, long> predecessors = new Dictionary<long, long>();
     21      visitedNodes = new HashSet<long>();        // visited
     22      unvisitedNodes = new HashSet<long>();      // unvisited
     23      distances = new Dictionary<long, float>();
     24      predecessors = new Dictionary<long, long>();
    1925
    20       long currentNode;
    21       Dictionary<long, float> currentNeighbors = new Dictionary<long, float>();
    2226      List<long> resultRoute = new List<long>();
    23 
    2427      if (sourceNodeId == targetNodeId) {
    2528        resultRoute.Add(sourceNodeId);
    … …  
    2730      }
    2831
    29       distances.Add(sourceNodeId, 0);
    30       unvisitedNodes.Add(sourceNodeId);
    31 
    32       currentNode = sourceNodeId;
    33       currentNeighbors = graph.GetNeighbors(currentNode);
     32      long currentNode = sourceNodeId;
     33      distances.Add(currentNode, 0);
     34      unvisitedNodes.Add(currentNode);
    3435
    3536      while (unvisitedNodes.Count > 0) {
    36         //Vertex node = getMinimum(unSettledNodes);
    37         //settledNodes.add(node);
    38         //unSettledNodes.remove(node);
    39         //findMinimalDistances(node);
    40 
    41         //currentNode = GetMinimum(unvisitedNodes);
     37        currentNode = GetMinimumDistance(unvisitedNodes);
    4238        visitedNodes.Add(currentNode);
    4339        unvisitedNodes.Remove(currentNode);
    44 
    4540        if (currentNode == targetNodeId) {
    4641          break;
    4742        }
    48 
    49         currentNeighbors = graph.GetNeighbors(currentNode);
    50 
     43        FindMinimalWeight(currentNode);
    5144      }
    5245
    … …  
    5447        // target was not found
    5548        // maybe throw exception
     49        throw new Exception(string.Format("No route found from {0} to {1}", sourceNodeId, targetNodeId));
    5650      }
    57       return resultRoute.ToArray();
     51      return GetRoute(targetNodeId).ToArray();
    5852    }
    5953
    6054    #endregion
    6155
    62     //private long GetMinimum(HashSet<long> nodeIds) {
    63     //  long minimum = -1;
    64     //  foreach (long id in nodeIds) {
    65     //    if (minimum == -1) minimum = id;
    66     //    else {
    67     //      if (GetDistance(id) < GetDistance(minimum)) {
    68     //        minimum = id;
    69     //      }
    70     //    }
    71     //  }
    72     //}
     56    private long GetMinimumDistance(HashSet<long> nodeIds) {
     57      long minimum = -1;
     58      foreach (long id in nodeIds) {
     59        if (minimum == -1) minimum = id;
     60        else {
     61          if (GetDistance(id) < GetDistance(minimum)) {
     62            minimum = id;
     63          }
     64        }
     65      }
     66      return minimum;
     67    }
     68
     69    private float GetDistance(long id) {
     70      float d;
     71      if (distances.TryGetValue(id, out d)) {
     72        return d;
     73      } else { return float.MaxValue; }
     74
     75    }
     76
     77    private void FindMinimalWeight(long nodeId) {
     78      Dictionary<long, float> currentNeighbors = graph.GetNeighbors(nodeId);
     79      foreach (KeyValuePair<long, float> neighbor in currentNeighbors) {
     80        // update relax
     81        float totalWeight = GetDistance(nodeId) + neighbor.Value;
     82        if (GetDistance(neighbor.Key) > totalWeight) {
     83          distances[neighbor.Key] = totalWeight;
     84          predecessors[neighbor.Key] = nodeId;
     85          unvisitedNodes.Add(neighbor.Key);
     86        }
     87      }
     88    }
     89
     90    private List<long> GetRoute(long nodeId) {
     91      List<long> route = new List<long>();
     92      long current = nodeId;
     93      long next;
     94
     95      if (!predecessors.TryGetValue(current, out next)) {
     96        return null;
     97      }
     98      route.Add(current);
     99      while (!predecessors.TryGetValue(current, out next)) {
     100        current = predecessors[current];
     101        route.Add(current);
     102      }
     103      route.Reverse();
     104      return route;
     105    }
    73106  }
    74107}
Note: See TracChangeset for help on using the changeset viewer.