fn() bellmanFordAlgorithm
Computes shortest paths from a single source in a directed graph.

Defined in <seqan/graph_algorithms.h>
Signature bool bellmanFordAlgorithm(g, source, weight, predecessor, distance)

Parameters

g A directed graph. Types: Directed Graph
source A source vertex. Types: VertexDescriptor
weight A weight map.A property map with edge weights. Edge weights may be negative.
predecessor A property map. A property map that represents predecessor relationships among vertices. It determines a shortest-paths tree.
distance A property map.Indicates for each vertex the distance from the source.

Return Values

bool true if the graph has no negative weight cycles, false otherwise.

Detailed Description

Edge weights may be negative in the Bellman-Ford algorithm. The out parameters are only valid if the algorithm returns true.

Example

#include <iostream>
#include <seqan/graph_algorithms.h>

using namespace seqan;

int main()
{
    typedef Graph<Directed<> > TGraph;
    typedef VertexDescriptor<TGraph>::Type TVertexDescriptor;
    typedef EdgeDescriptor<TGraph>::Type TEdgeDescriptor;
    typedef Size<TGraph>::Type TSize;

    // Create graph with 10 directed edges (0,1), (0,3), ...
    TSize numEdges = 10;
    TVertexDescriptor edges[] = {0,1, 0,3, 1,2, 1,3, 2,4, 3,1, 3,2, 3,4, 4,0, 4,2};
    TGraph g;
    addEdges(g, edges, numEdges);

    // Print graph.
    std::cout << g << "\n";

    // Create external edge property map and assign to graph.
    unsigned weights[] =    {10, 5, 1, 2, 4, 3, 9, 2, 7, 6};
    String<unsigned> weightMap;
    assignEdgeMap(g, weightMap, weights);

    // Run Bellman-Ford algorithm from vertex 0.  NB: Ford-Fulkerson also
    // detects negative cycles.
    String<unsigned int> predMap;
    String<unsigned int> distMap;
    bool noNegativeCycle = bellmanFordAlgorithm(g,0,weightMap,predMap,distMap);

    // Print result to stdout.
    std::cout << "Single-Source Shortest Paths: " << "\n"
              << "Graph without negative cycles? " << noNegativeCycle << "\n";
    typedef Iterator<TGraph, VertexIterator>::Type TVertexIterator;
    TVertexIterator it(g);
    while(!atEnd(it))
    {
        std::cout << "Path from 0 to " << getValue(it) << ": ";
        _printPath(g,predMap,(TVertexDescriptor) 0, getValue(it));
        std::cout << " (Distance: " << getProperty(distMap, getValue(it)) << ")\n";
        goNext(it);
    }

    return 0;
}
Adjacency list:
0 -> 3,1,
1 -> 3,2,
2 -> 4,
3 -> 4,2,1,
4 -> 2,0,
Edge list:
Source: 0,Target: 3 (Id: 1)
Source: 0,Target: 1 (Id: 0)
Source: 1,Target: 3 (Id: 3)
Source: 1,Target: 2 (Id: 2)
Source: 2,Target: 4 (Id: 4)
Source: 3,Target: 4 (Id: 7)
Source: 3,Target: 2 (Id: 6)
Source: 3,Target: 1 (Id: 5)
Source: 4,Target: 2 (Id: 9)
Source: 4,Target: 0 (Id: 8)

Single-Source Shortest Paths: 
Graph without negative cycles? 1
Path from 0 to 0: 0 (Distance: 0)
Path from 0 to 1: 0,3,1 (Distance: 8)
Path from 0 to 2: 0,3,1,2 (Distance: 9)
Path from 0 to 3: 0,3 (Distance: 5)
Path from 0 to 4: 0,3,4 (Distance: 7)

See Also