0
我正在尋找一種方法來在我的Boost圖庫應用程序中使用有向圖來包含轉彎限制和/或轉向處罰。我需要限制例如U形轉彎（如果這是最好的方式，這可能是非常高的罰分）。Boost Graph Library轉向限制或轉向處罰
我在Boost Graph中找不到明確的機制來添加這樣的懲罰/限制，那麼處理轉彎限制的最佳方法是什麼？
我到目前爲止看到的唯一解決方案是擴大圖形的'內部邊緣'，用於頂點中的每個可能的轉彎，忽略限制轉彎的'內部邊緣'。這對我來說似乎非常蠻橫，有沒有更好的辦法？
實施例圖： 
假設有兩個源A和E，以及使用迪傑斯特拉（見下面的代碼示例）被計算爲每個頂點的最短路徑。
兩個最短路徑樹（printShortestPath的輸出（））：
Shortest path from A to all vertices:
distances and parents:
distance(A) = 0, parent(A) = A
distance(B) = 100, parent(B) = A
distance(C) = 200, parent(C) = B
distance(D) = 200, parent(D) = B
distance(E) = 1.79769e+308, parent(E) = E
-------------
Shortest path from E to all vertices:
distances and parents:
distance(A) = 1.79769e+308, parent(A) = A
distance(B) = 100, parent(B) = E
distance(C) = 200, parent(C) = B
distance(D) = 200, parent(D) = B
distance(E) = 0, parent(E) = E
什麼是優雅的方式在升壓禁止這個轉折點（E1至E4）::圖？
一個簡單的解決辦法是擴大圖有代表轉向運動（與禁止四類成本高）額外的邊緣，但我希望有一個更優雅的方式。
代碼：
#include <boost/config.hpp>
#include <iostream>
#include <boost/graph/graph_traits.hpp>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/dijkstra_shortest_paths.hpp>
#include <QString>
#include <vector>
using namespace boost;
struct GraphNode
{
GraphNode() {}
GraphNode(const QString& name_):name(name_) {}
QString name;
};
struct GraphLink
{
GraphLink() {}
GraphLink(const QString& name_, double length_, double travelTime_):name(name_),length(length_), travelTime(travelTime_) {}
QString name;
double length; // in meters
double travelTime; // in seconds
};
typedef boost::adjacency_list<boost::listS, boost::vecS, boost::directedS, GraphNode, GraphLink> NetworkGraph;
typedef graph_traits <NetworkGraph>::vertex_descriptor vertex_descriptor;
typedef std::vector<decltype (GraphLink::length)> distancesT;
void printShortestPath (const NetworkGraph& map, distancesT distances,std::vector<vertex_descriptor> p)
{
std::cout << "distances and parents:" << std::endl;
graph_traits <NetworkGraph>::vertex_iterator vi, vend;
for (auto vs=vertices(map); vs.first!=vs.second;++vs.first)
{
auto currEdge=map[*vs.first];
auto parent=p[*vs.first];
QString parentName=map[parent].name;
QString name =currEdge.name;
std::cout << "distance(" << name.toStdString() << ") = " << distances[*vs.first] << ", ";
std::cout << "parent(" << name.toStdString() << ") = " << parentName.toStdString() << std::
endl;
}
}
int main(int, char *[])
{
//Create the vertices
NetworkGraph map;
NetworkGraph::vertex_descriptor vertexA = add_vertex(map);
map[vertexA].name ="A";
NetworkGraph::vertex_descriptor vertexB = add_vertex(map);
map[vertexB].name ="B";
NetworkGraph::vertex_descriptor vertexC = add_vertex(map);
map[vertexC].name ="C";
NetworkGraph::vertex_descriptor vertexD = add_vertex(map);
map[vertexD].name ="D";
NetworkGraph::vertex_descriptor vertexE = add_vertex(map);
map[vertexE].name ="E";
// Create the edges
NetworkGraph::edge_descriptor e1 = add_edge(vertexA,vertexB,map).first;
map[e1].name ="e1";
map[e1].length =100.0;
NetworkGraph::edge_descriptor e2 = add_edge(vertexB,vertexC,map).first;
map[e2].name ="e2";
map[e2].length =100.0;
NetworkGraph::edge_descriptor e3 = add_edge(vertexC,vertexD,map).first;
map[e3].name ="e3";
map[e3].length =100.0;
NetworkGraph::edge_descriptor e4 = add_edge(vertexB,vertexD,map).first;
map[e4].name ="e4";
map[e4].length =100.0;
NetworkGraph::edge_descriptor e5 = add_edge(vertexE,vertexB,map).first;
map[e5].name ="e5";
map[e5].length =100.0;
distancesT distances (num_vertices(map)); // distances
std::vector<vertex_descriptor> p (num_vertices(map)); // parents
//calculate shortest paths from vertex A using Dijkstra, based on GraphLink::length as edge cost
dijkstra_shortest_paths (map,
vertexA,
weight_map (get(&GraphLink::length, map))
.distance_map (make_iterator_property_map(distances.begin(), get(vertex_index, map)))
.predecessor_map (make_iterator_property_map(p.begin(), get(vertex_index, map))));
std::cout << "Shortest path from A to all vertices: " << std::endl;
printShortestPath (map, distances, p);
//calculate shortest paths from vertex E using Dijkstra, based on GraphLink::length as edge cost
dijkstra_shortest_paths (map,
vertexE,
weight_map (get(&GraphLink::length, map))
.distance_map (make_iterator_property_map(distances.begin(), get(vertex_index, map)))
.predecessor_map (make_iterator_property_map(p.begin(), get(vertex_index, map))));
std::cout << "-------------" << std::endl;
std::cout << "Shortest path from E to all vertices: " << std::endl;
printShortestPath (map, distances, p);
return EXIT_SUCCESS;
}
