Bellman-ford 알고리즘의 작업에서의 이상 함

Question

-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; 
} 

누구가 알고리즘을 이해합니다. 내 실수는 어디 있니?

Answer 1

-log 페널티 기능은 일반적으로 1.0 이하의 독립 확률에 사용됩니다.

-log (number_greater_than_one) = negative_number이므로 음수 점수가있는 경로가 있습니다.

Answer 2

부정적인주기가있는 경우 정의에 따라 연결된 경로를 무한히 음한 비용으로 만들 수 있습니다 (주기를 무한 루프로 반복). 그것은 오류 조건입니다.