Graph Algorithm Question


A

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
 
Ad

Advertisements

S

Steve Horsley

Anna said:
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
 
Ad

Advertisements

M

Mladen Adamovic

Anna Smith said:
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
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Top