BellmanFord

<< DiscreteMath`Combinatorica`

Several users have pointed out an error in BellmanFord that also effects ShortestPath. Here is an example from Dr. Yehuda Ben-Shimol that illustrates this error.

elist = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 5}, {2, 
            8}, {3, 5}, {3, 6}, {3, 7}, {4, 5}, {4, 6}, {4, 8}, {5, 6}, {5, 
            7}, {6, 7}, {6, 8}, {7, 8}};
wlist = {2, 3, 7, 8, 15, 9, 12, 11, 4, 19, 18, 1, 5, 13, 16, 14, 17, 
          10, 20};

Generating a basic graph

g = SetEdgeWeights[FromUnorderedPairs[elist], elist, wlist]

Present the results graphically

Show[
      GraphicsArray[{ShowGraph[
            ShortestPathSpanningTree[g, 2, Algorithm -> Dijkstra], 
            PlotLabel -> 
              StyleForm["Shortest Path from vertex 2\nDijkstra \
Algorithm", FontSize -> 14, FontFamily -> "Times", 
                FontWeight -> "Bold"], DisplayFunction -> Identity, 
            VertexNumber -> On], 
          ShowGraph[
            ShortestPathSpanningTree[g, 2, Algorithm -> BellmanFord], 
            PlotLabel -> 
              StyleForm["Shortest Path from vertex 2\nBellmanFord Algorithm\
", FontSize -> 14, FontFamily -> "Times", FontWeight -> "Bold"], 
            DisplayFunction -> Identity, VertexNumber -> On]}], 
      DisplayFunction -> $DisplayFunction]

Look Closely what is returened by each algorithm

BellmanFord[g, 2]

Dijkstra[g, 2]

You may easily see that the distance between vertices 1 and 2 should be 2 (which is the weight of the edge {1,2} and not 19 as returned by the Bellman Ford implementation.

Now I quit the kernel and load NewCombinatorica.m and try the same example.

Quit[]

<< NewCombinatorica.m

elist = {{1, 2}, {1, 3}, {1, 4}, {1, 5}, {1, 6}, {2, 3}, {2, 5}, {2, 
            8}, {3, 5}, {3, 6}, {3, 7}, {4, 5}, {4, 6}, {4, 8}, {5, 6}, {5, 
            7}, {6, 7}, {6, 8}, {7, 8}};
wlist = {2, 3, 7, 8, 15, 9, 12, 11, 4, 19, 18, 1, 5, 13, 16, 14, 17, 
          10, 20};

g = SetEdgeWeights[FromUnorderedPairs[elist], elist, wlist]

Show[
      GraphicsArray[{ShowGraph[
            ShortestPathSpanningTree[g, 2, Algorithm -> Dijkstra], 
            PlotLabel -> 
              StyleForm["Shortest Path from vertex 2\nDijkstra \
Algorithm", FontSize -> 14, FontFamily -> "Times", 
                FontWeight -> "Bold"], DisplayFunction -> Identity, 
            VertexNumber -> On], 
          ShowGraph[
            ShortestPathSpanningTree[g, 2, Algorithm -> BellmanFord], 
            PlotLabel -> 
              StyleForm["Shortest Path from vertex 2\nBellmanFord Algorithm\
", FontSize -> 14, FontFamily -> "Times", FontWeight -> "Bold"], 
            DisplayFunction -> Identity, VertexNumber -> On]}], 
      DisplayFunction -> $DisplayFunction]

BellmanFord[g, 2]

Dijkstra[g, 2]