Changeset 8539


Ignore:
Timestamp:
08/29/12 18:18:53 (7 years ago)
Author:
spimming
Message:

#1894:

  • Dijkstra version with no decrease key
  • used wrong index in BinHeap implementation
  • implement interface in BinaryHeap
Location:
branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3
Files:
1 added
3 edited

Legend:

Unmodified
Added
Removed
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/HeuristicLab.Algorithms.GraphRouting.csproj

    r8527 r8539  
    6161    <Compile Include="AStarAlgorithmV4.cs" />
    6262    <Compile Include="AStarAlgorithmV5.cs" />
     63    <Compile Include="DijkstraNoDecAlgorithm.cs" />
    6364    <Compile Include="DijkstraAlgorithmV2.cs" />
    6465    <Compile Include="GraphRoutingAlgorithm.cs" />
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinHeap.cs

    r8527 r8539  
    9292      while ((left < size - 1 && data[idx].Key.CompareTo(data[left].Key) != -1) ||
    9393             (right < size - 1 && data[idx].Key.CompareTo(data[right].Key) != -1)) {
    94         if ((right >= size - 1) || (data[idx].Key.CompareTo(data[right].Key) == -1)) {
     94        if ((right >= size - 1) || (data[left].Key.CompareTo(data[right].Key) == -1)) {
    9595          Swap(left, idx);
    9696          idx = left;
  • branches/RoutePlanning/HeuristicLab.Algorithms.GraphRouting/3.3/PriorityQueues/BinaryHeap.cs

    r8527 r8539  
    11
    22using System;
     3using System.Collections.Generic;
     4using HeuristicLab.Algorithms.GraphRouting.Interfaces;
    35namespace HeuristicLab.Algorithms.GraphRouting.PriorityQueues {
    46  // implementation based on C++ version from Peter Sanders
    57  // http://www.mpi-inf.mpg.de/~sanders/programs/spq/
    6   public sealed class BinaryHeap<K, V> where K : IComparable {
     8  public sealed class BinaryHeap<K, V> : IHeap<K, V> where K : IComparable {
    79    private class KNElement {
    810      public K Key { get; set; }
     
    3133    public int Size {
    3234      get { return size; }
     35    }
     36
     37    public KeyValuePair<K, V> PeekMin() {
     38      if (size == 0) {
     39        throw new InvalidOperationException("Heap is empty");
     40      }
     41      return new KeyValuePair<K, V>(data[1].Key, data[1].Value);
    3342    }
    3443
Note: See TracChangeset for help on using the changeset viewer.