Method FindShortestPath

tools/openlr/score_paths_connector.cpp:213–290

}

bool ScorePathsConnector::FindShortestPath(Graph::Edge const & from, Graph::Edge const & to, LinearSegmentSource source,
                                           FunctionalRoadClass lowestFrcToNextPoint, uint32_t maxPathLength,
                                           Graph::EdgeVector & path)
{
  double constexpr kLengthToleranceFactor = 1.1;
  uint32_t constexpr kMinLengthTolerance = 20;
  uint32_t const lengthToleranceM =
      max(static_cast<uint32_t>(kLengthToleranceFactor * maxPathLength), kMinLengthTolerance);

  struct State
  {
    State(Graph::Edge const & e, uint32_t const s) : m_edge(e), m_score(s) {}

    bool operator>(State const & o) const { return tie(m_score, m_edge) > tie(o.m_score, o.m_edge); }

    Graph::Edge m_edge;
    uint32_t m_score;
  };

  CHECK(from.HasRealPart() && to.HasRealPart(), ());

  priority_queue<State, vector<State>, greater<>> q;
  map<Graph::Edge, double> scores;
  map<Graph::Edge, Graph::Edge> links;

  q.emplace(from, 0);
  scores[from] = 0;

  while (!q.empty())
  {
    auto const state = q.top();
    q.pop();

    auto const & stateEdge = state.m_edge;
    // TODO(mgsergio): Unify names: use either score or distance.
    auto const stateScore = state.m_score;

    if (stateScore > maxPathLength + lengthToleranceM)
      continue;

    if (stateScore > scores[stateEdge])
      continue;

    if (AreEdgesEqualWithoutAltitude(stateEdge, to))
    {
      for (auto edge = stateEdge; edge != from; edge = links[edge])
        path.emplace_back(edge);
      path.emplace_back(from);
      reverse(begin(path), end(path));
      return true;
    }

    Graph::EdgeListT edges;
    m_graph.GetOutgoingEdges(stateEdge.GetEndJunction(), edges);
    for (auto const & edge : edges)
    {
      if (source == LinearSegmentSource::FromLocationReferenceTag &&
          !ConformLfrcnpV3(edge, lowestFrcToNextPoint, m_infoGetter))