Я не могу понять, что не так, если указать -log () вес показывает «отрицательный цикл». если удалить log (), алгоритм работает, но нет отрицательного цикла
int main() {
typedef double Weight;
typedef property<edge_weight_t, Weight> WeightProperty;
typedef property<vertex_name_t, string> NameProperty;
typedef adjacency_list < listS, vecS, directedS, NameProperty, WeightProperty > Graph;
typedef property_map < Graph, vertex_index_t >::type IndexMap;
typedef property_map < Graph, vertex_name_t >::type NameMap;
typedef graph_traits < Graph >::vertex_descriptor Vertex;
typedef iterator_property_map < Vertex*, IndexMap, Vertex, Vertex& > PredecessorMap;
typedef iterator_property_map < Weight*, IndexMap, Weight, Weight& > DistanceMap;
// Create a graph
Graph g;
graph_traits<Graph>::vertex_descriptor A = add_vertex(string("A"),g);
graph_traits<Graph>::vertex_descriptor B = add_vertex(string("B"),g);
graph_traits<Graph>::vertex_descriptor C = add_vertex(string("C"),g);
graph_traits<Graph>::vertex_descriptor D = add_vertex(string("D"),g);
add_edge(A, B, -log(0.741), g);
add_edge(A, C, -log(0.657), g);
add_edge(A, D, -log(1.061), g);
add_edge(B, A, -log(1.350), g);
add_edge(B, C, -log(0.888), g);
add_edge(B, D, -log(1.433), g);
add_edge(C, A, -log(1.521), g);
add_edge(C, B, -log(1.126), g);
add_edge(C, D, -log(1.614), g);
add_edge(D, A, -log(0.943), g);
add_edge(D, B, -log(0.698), g);
add_edge(D, C, -log(0.620), g);
property_map<Graph, edge_weight_t>::type weight_pmap = get(edge_weight_t(), g);
int nb_vertices = num_vertices(g);
int inf = (numeric_limits<int>::max)();
vector<float> distance(nb_vertices, inf);
vector<size_t> parent(nb_vertices);
for (size_t i = 0; i<nb_vertices; ++i)
parent[i] = i;
//starting vertex
distance[B] = 0;
//bool r = bellman_ford_shortest_paths(g, nb_vertices, weight_pmap, &parent[0], &distance[0],closed_plus<int>(), std::less<int>(), default_bellman_visitor());
bool r = bellman_ford_shortest_paths(g, nb_vertices, weight_map(weight_pmap).distance_map(&distance[0]).predecessor_map(&parent[0]));
if (r)
for (size_t i = 1; i<nb_vertices; ++i)
cout << distance[i] << endl;
else
cout << "negative cycle" << endl;
return EXIT_SUCCESS;
}
Кто разбирается в алгоритмах. скажи где моя ошибка?
Функция штрафа -log обычно используется для независимых вероятностей, которые по определению меньше 1,0.
-log (number_greater_than_one) = отрицательный номер, поэтому у вас есть пути с отрицательным счетом.
Если есть отрицательный цикл, то по определению вы можете сделать любой связанный путь бесконечно отрицательной стоимостью (просто бесконечный цикл по циклу). Это условие ошибки.