search

LdDl / ch

Contraction Hierarchies (with bidirectional version of Dijkstra's algorithm) technique for computing shortest path in graph.
Apache License 2.0
46 stars 5 forks source link

replace int64 with ContractionPath + eliminate duplicates from contra… #16

Closed LdDl closed 3 years ago

LdDl commented 3 years ago
  1. Replace map[int64]map[int64]int64 with map[int64]map[int64]*ContractionPath. ContractionPath - is vertex id + contraction's cost
  2. Eliminate duplicates from contractions reference file
LdDl commented 3 years ago
  1. Excess edges writing: Both writing outcoming and incoming adjacent is not necessary
LdDl commented 3 years ago
  1. Update ComputePath() function: 
    l.InsertAfter(contractedNode.ViaVertex, e)