Graph Algorithm Question

[Anna Smith]

Hi Folks,

Given a directed graph, is there an algorithm to do the following:

1) Shortest path: the answer is simple. dijkstra algorithm.

2) Given a directed graph, and there is no edge starting and ending at
a node X, can we still used Dijkstra's algorithm to find the shortest
path from X to X.


Here is where I need some help.

1) Give a two nodes, how do we find out the number of paths and the
number of hops between the two paths?

2) Given a sequence of nodes say N1-N5-N3-N4-N2, how do we find out
sum of the weights along the edges. This needs to be done
progamatically.


Any good sites with sample java code or a good java data structures
book?

Thanks,
Anna

 

[Steve Horsley]

Hi Folks,

Given a directed graph, is there an algorithm to do the following:

1) Shortest path: the answer is simple. dijkstra algorithm.

2) Given a directed graph, and there is no edge starting and ending at
a node X, can we still used Dijkstra's algorithm to find the shortest
path from X to X.


Here is where I need some help.

1) Give a two nodes, how do we find out the number of paths and the
number of hops between the two paths?

2) Given a sequence of nodes say N1-N5-N3-N4-N2, how do we find out
sum of the weights along the edges. This needs to be done
progamatically.


Any good sites with sample java code or a good java data structures
book?

Thanks,
Anna
http://www.google.com/search?q=java+Dijkstra+algorithm

9000 hits

Steve

 

[Mladen Adamovic]

1) Give a two nodes, how do we find out the number of paths and the
number of hops between the two paths?

IMHO, you should immitate "fill algorithm" but for graphs. Each time "fill"
find path between X and Y,
put that path in ArrayList PathsArrayList.
Then, to find number of hops between the two paths for each paar of nodes
for two paths in that PathsArrayList find minimum distance in nodes and that
should be hop, isn't it?

2) Given a sequence of nodes say N1-N5-N3-N4-N2, how do we find out
sum of the weights along the edges. This needs to be done
progamatically.

Make some int Graphs.getWeight(Node n1,Node n2) algorithm (find distance
between n1 and n2 in the table of node distances), then you just sum all
graphs weights. Shouldn't be complicated at all.

Any good sites with sample java code or a good java data structures
book?

I saw a lot, but some of them aren't free. google and amazon