Re: Bellman-Ford Query

[Yoann Pigné <yoann.pigne AT gmail.com>]

Hi, 

I don’t know what your graph looks like. Would you mind sharing that graph 
too?

My guess is nodes 1 and 2 are connected through a directed edge (an arc) from 
1 to 2, so that a path from 1 to 2 exists but not from 2 to 1. The cost of 
the path from 2 to 1 must be infinity but the length of the path is zero 
because their is no path. Again, just a guess.

Yoann 

> Le 16 mars 2018 à 10:52, Acarali, Dilara 
> <Dilara.Acarali AT city.ac.uk>
>  a écrit :
> 
> Hello, 
> 
> I've been using GraphStream, and specifically exploring the Bellman-Ford 
> algorithm implementation to find distance between nodes on a simple graph.  
> I run the algorithm and print the results as follows:
> 
> connection  length  path      
> 1->1        0.0     []        
> 1->2        1.0     [2, 1]    
> 1->3        2.0     [3, 2, 1] 
> 1->4        1.0     [4, 1]    
> 1->5        2.0     [5, 4, 1] 
> 1->6        1.0     [6, 1]    
>  
> 2->1        0.0     []        
> 2->2        0.0     []        
> 2->3        1.0     [3, 2]    
> 2->4        1.0     [4, 1]    
> 2->5        2.0     [5, 3, 2] 
> 2->6        1.0     [6, 2]    
> 
> 3->1        0.0     []        
> 3->2        1.0     [2, 1]    
> 3->3        0.0     []        
> 3->4        1.0     [4, 1]    
> 3->5        1.0     [5, 3]    
> 3->6        1.0     [6, 3]    
> 
> The code I use looks like this:
> 
> for (Node srcNode : graph.getEachNode()) {
>    BellmanFord presimBellman = new BellmanFord("hops", srcNode.getId());
>    presimBellman.init(graph);
>    presimBellman.compute();
> for (Node dstNode : graph.getEachNode()) {
> String connection = "" + srcNode.getId() + "->" + dstNode.getId();
> double pathLength = presimBellman.getShortestPath(dstNode).getNodeCount();
> Path path = presimBellman.getShortestPath(dstNode);
>           }
> }
> 
> My question is, why does 1->2 return the correct hop count of 1, but 2->1 
> does not? I tried setting both node1 and node2 as the source node in the 
> Bellman-Ford constructor (on alternative runs) and still get the same 
> result. I am aware that this is a stub implementation but don't think this 
> should be happening? 
> 
> I also get the same result when I run:
> 
> BellmanFord testBellman = new BellmanFord("hops", "2");
> testBellman.init(graph);
> testBellman.compute();
> System.out.println(testBellman.getSource() + "->1 = " + 
> testBellman.getShortestPathValue(1));
> 
> Any feedback would be much appreciated.
> 
> Regards
> 
> Dilara