Re: Graph Algorithm Question

From: Bilal Sallakh (afkar_at_mail2world.com)
Date: 04/25/04 

Date: 24 Apr 2004 15:01:27 -0700

anna_smith515@yahoo.com (Anna Smith) wrote in message news:<8062c548.0404240743.19c2f9e8@posting.google.com>...
> Hi Folks,
>
> Given a directed graph, is there an algorithm to do the following:
>
> 1) Shortest path: the answer is simple. dijkstra algorithm.

You have missed a very important condition in your description:

Are all the weights positive?

If so, then the answer will be simple and Dijkstra's algorithm will
work correctly.

If not then you may use the Bellman-Ford algorithm found in most
Algorithms textbooks. However the graph should contain no directed
cycle whose weight is negative.

>
> 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.
>
You mean there are no self-loops.

If all the edges weighs are positive then shortest path from X to X is
the Path of length 0 (You will stay in X) and weight 0, since if there
is a loop from X to X, its weight will be necessarily positive which
is not less than the previous trivial 0-length path.
So there is no need to use an algorithm, but if you used Dijkstra's
algorithm with X as a start node, then d[X] = 0 (the cost to go from X
to X) and Pi[X] = nil (indicating that there is no predesessor of X in
the shortest path that goes from X to X).

If not, then there are two cases:
1- There are loops whose weight are negative and are reachable from
the source: If there is a path from the starting node S to a node X
that pass through the Negative weight loop, then the shortest path
from S to X is not well defined.
2- If there are no loops whose weight are negative, then again the
shortest path from the node to itself will be a 0-length trivial path.
(No need to apply an algorithm).

>
> 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?

Finding the number of paths between to nodes should be constrained:

If there is a path from u to v that pass through a vertex x and x is a
member of a cycle, then there are infinite number of paths from u to
v.

If not then I think we can find an algoithm that count (and optionally
find) all the paths from u to v. I am suspicious that it may be
NP-Complete (Very slow when the graph has many nodes). In the worst
case we may try and error using a backtracking algorithm.

>
> 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.
>

Computing the weight of the sequence assuming there is an edge between
each adjacent pair is very easy!. According to your data structure
htat represent the weighted graph (Adjcency matrix, Adjcency lists,
Incidence matrix, ...) just iterate on the edge accumlating their
weights in a variable...

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

Okay, you may have a comprehensive idea after you read a textbook on
Graph Algorithms:

The book Introduction to Algorithm (Cormen, LEISERSON, RIVEST) is very
nice and clear, and as I remember its available as a .pdf file on the
web (an old version but still good).

The book Algorithms in Java (Robert Sedjwick (may be misspelled)) is
also good and has a thorough dicussion on the Shortest Paths Problem
with Java code.
>
> Thanks,
> Anna

Quantcast