Boost BGL Dijkstra 最短路径算法

Question

我不熟悉boost库，正在尝试学习。 我已经使用boost图形库调用dijstra的最短路径函数，在地图上查找到达目的地的路径。顶点是交叉口，边缘是街道段。

我通过最小时间找到最短路径。为此，我定义了边缘权重作为时间，时间= st段长度*其速度/限制。这确实给了我最短路径（按时间计算）但是我还要考虑转弯并将每个转弯的总时间增加15秒钟。如何检测转弯是指如果第二条街道段（边）的st名称与第一条不相等，则为转弯。

基本上，我想动态分配权重（不仅像我在这里所做的那样在开始时设置）。当程序在搜索过程中访问边缘时，我希望它在这个阶段检查父项（或前任者）。如何传递一个函数或其他参数来执行此操作？

vector<unsigned>  OurGraph::find_awesome_path(unsigned start, unsigned finish)
{

    // start and finish are intersection IDs,
    // Get the corresponding Vertices in the graph. 
    Vertex start_node = vertex_map[start]; 
    Vertex dest_node = vertex_map[finish];   

    std::vector<Vertex> predecessors(boost::num_vertices(my_graph)); // To store parents
    std::vector<float> distances(boost::num_vertices(my_graph)); // To store dijkstra distances

    IndexMap indexMap = boost::get(boost::vertex_index, my_graph);
    PredecessorMap predecessorMap(&predecessors[0], indexMap);
    DistanceMap distanceMap(&distances[0], indexMap);

    boost::dijkstra_shortest_paths(my_graph, start_node, boost::distance_map(distanceMap).predecessor_map(predecessorMap));
vector<Edge> path;

    path = get_edge_path(dest_node, predecessorMap);    // Extracts edges from edge descriptors in predecessor map
                                                    // and piles them in a vector of Edge. 
    return segment_list_from_edges(path);           // Convert edges to street segment IDs and return.
}

其中my_graph是类型Graph，Graph、Vertex、Edge、IndexMap、PredecessorMap和DistanceMap被定义为以下类型：

typedef boost::property<boost::edge_weight_t, float> WeightProperty;
typedef boost::property<boost::vertex_name_t, unsigned> IntersectionProperty;  
typedef boost::adjacency_list < boost::listS, boost::vecS, boost::directedS,
  IntersectionProperty, WeightProperty > Graph;
typedef boost::graph_traits < Graph >::vertex_descriptor Vertex;
typedef boost::graph_traits < Graph >::edge_descriptor Edge;
typedef boost::property_map < Graph, boost::vertex_index_t >::type IndexMap;
typedef boost::iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
typedef boost::iterator_property_map < float*, IndexMap, float, float& > DistanceMap;

- Noobification

---

你可能不能直接使用Dijkstra算法，因为它假设通过某条边行进所产生的额外成本与到达起始顶点的方式无关。为了解决这个问题，你可以在同一条街道上的每对非相邻顶点u和v之间添加额外的边，然后将15秒钟的时间添加到每条边的成本中（新边仅包括15秒钟的成本）。最后，从任何解决方案中减去15秒钟。注意：如果所有n个顶点都属于同一条路，则可能会产生O(n^2)额外的边缘。 - j_random_hacker

我并没有完全理解建议。 根据我的有限理解，我分别进行了以下操作： （1） 添加额外的边以短路形成拐角的顶点。 （2） 在位于同一街道上的顶点上添加额外的边。 （3） 分配权重不同的值，包括大大小小的常数、当前或下一段的长度、当前或下一段的时间等。它们要么返回非法路径（包括这些额外的边），要么没有任何影响，要么返回更糟糕的路径。 - Noobification

（2）最接近正确。对于任何一对在同一条道路上但不相邻的顶点u和v，您需要添加一条边：这条边的目的是允许Dijkstra从原始图中选择相应的边系，同时只支付25s的转向成本一次。例如，如果您在同一条道路上有5个顶点a、b、c、d、e，则会添加边ac、bd、ce、ad、be、ae，每个边的成本都等于它们“跨越”的边的成本之和+25（例如，be的成本将是bc的成本+cd的成本+de的成本+25）。所有原始边的成本也增加了25。 - j_random_hacker

如果Dijkstra算法在其解决方案中包含其中一条额外的边，则意味着它所“跨越”的原始边集（例如，添加的边跨越了原始边bc、cd和de）是最短路径的一部分，并且考虑了转弯。 - j_random_hacker

在新版本的图中，每一条边都会额外花费25秒。我们的想法是原图中每一个没有转弯的子路径都对应着新图中的一条边，而额外的25秒则是这个子路径开头所需的拐弯费用。（最终的解答需要减去25秒，因为开头不需要拐弯。）虽然在新图中可能存在像ac->ce这样的路径，它会额外收费25秒，即使它并没有离开同一条道路，但Dijkstra算法永远不会选择这样做，因为我们已经确保了已经存在更便宜的单边路径ae。 - j_random_hacker

由于时间限制，我们将继续使用现有的有缺陷版本。我会尝试你说的并稍后回复你哈哈。感谢你的帮助。 - Noobification

Answer 1

一种方法是使用差分图。在这种情况下，差分图中的每个顶点都相当于当前图中的一条边。因此，一个顶点可以封装一个转弯，例如。然后，您可以将涉及街道名称更改（或您用于确定转弯的任何机制）的转弯权重添加到边缘中。

- Brandon Kohn