Subject: Re: Book on calculating two alternative shortest paths

From: Fred Baker <[email-masked]>
Date: Mon, 22 Jan 2001 12:02:59 +0100

At 08:09 PM 1/21/01 -0800, Wushao Wen wrote:
>I remember there is a book or paper on how to calculate two shortest
>paths from a source to a destination in a mesh network. The author also
>mention it in this mailing list. Can someone please tell me the book name
>or the author name?

there are a number of them. What I would suggest is starting from the 
Collected Algorithms of the ACM, Algorithm named "Shortest Path First", 
dated 1968, and modify it a bit. It will, if recollection serves, calculate 
all paths through the mesh between here and there, producing them in the 
order "shortest first" for some definition of "short". What I think you 
want to do is add some "yes, that is shortest, but has some disqualifying 
characteristic" code, and probably some administrative metric code, to 
reject the first few you calculate. The first one you wind up with that 
meets your criteria is your happy route.

These appear to be on-line at 
http://www.mirror.ac.uk/sites/netlib.bell-labs.com/netlib/toms/

---

From: "Martin, Christian" <[email-masked]>
Date: Mon, 22 Jan 2001 09:12:22 -0500

This paper details an algorithm for finding diverse shortest paths in both
edge and vertex redundant graphs.

Redundant Trees for Preplanned Recovery in Arbitrary Vertex-Redundant or
Edge-Redundant Graphs  

 Transactions on Networking  October 1999 

 We present a new algorithm which creates redundant trees on arbitrary
node-redundant or link-redundant networks. These trees are such that any
node is connected to the common root of the trees by at least one of the
trees in case of node or link failure. Our scheme provides rapid preplanned
recovery of communications with great flexibility in the topology design.
Unlike previous algorithms, our algorithm can establish two redundant trees
in the case of a node failing in the network. In the case of failure of a
communications link, our algorithm provides a superset of the previously
known trees. 
 Muriel Medard, Member, IEEE, Steven G. Finn, Member, IEEE, Richard A.
Barry, and Robert G. Gallager, Life Fellow, IEEE 

http://www.comsoc.org/ieee/comsoc/abstract.asp?article_id=5624

This paper is more of a design instruction on how to build networks that can
reroute in the event of a node and or link failure.  May be of use.

Requires Comsoc Digital Library access.

Regards,
chris

> -----Original Message-----
> From: Wushao Wen [mailto:[email-masked]]
> Sent: Sunday, January 21, 2001 11:10 PM
> To: [email-masked]
> Subject: Book on calculating two alternative shortest paths
> 
> 
> Hi,
>    Thank you  very much!
> Wushao Wen

---

From: jie yang ee stnt <[email-masked]>
Date: Mon, 22 Jan 2001 09:51:49 -0500 (EST)

Hi, Wushao,
here is the book information you might be looking for.
Jie

----- Begin Included Message -----

>From [email-masked] Thu Jan  4 13:35 EST 2001
X-Accept-Language: en
MIME-Version: 1.0
To: jie yang ee stnt <[email-masked]>
Subject: Re: Routing
Content-Transfer-Encoding: 7bit

Hi,

You can order the book online at amazon.com or fatbrain.com, but it may take
a few weeks
to get it. If you want it right away, you may want to call the publisher,
Kluwer,
directly at (781) 871-6600. They should be able to ship it immediately. The
ISBN is
0-7923-8381-8.

If you have any problems, let me know.

Ramesh

> } From [email-masked] Thu Jan  4 12:03 EST 2001
> } X-Accept-Language: en
> } MIME-Version: 1.0
> } To: [email-masked]
> } CC: jie yang ee stnt <[email-masked]>, [email-masked]
> } Subject: Re: Routing
> } Content-Transfer-Encoding: 7bit
> }
> } You can also look up my book "Survivable Networks:Algorithms for Diverse
Routing",
> } Kluwer (1999) for concepts on traffic splitting over a number of
disjoint paths
> } (inclduing algorithms for their determinations within a given network)),
and full
> } restoration, when a link or node fails.
> }
> } Ramesh Bhandari

----- End Included Message -----

----- End Included Message -----

---

From: "Sinha, Rakesh" <[email-masked]>
Date: Tue, 23 Jan 2001 16:43:32 -0800

A number of approximation algorithms (i.e. efficient algorithms with
guaranteed performance bound) for similar problems are described in Chapter
six of the book "Approximation algorithms for NP-hard problems", edited by
Dorit S. Hochbaum, PWS publishing company.
The book describes the problem in terms of k-connectivity which is
equivalent (by something called Menger's theorem) to having k disjoint
paths. 

regards,
---------------
Rakesh K. Sinha
Ciena Core Switching Division
10480 Ridgeview Court, Cupertino, CA 95014
Ph: (408) 366 4950, Fax: (408) 366 4867
email: [email-masked] 

> Manohar Ellanti wrote:
> > Wushao Wen,
> >  original work on this problem is done by Sururballe that 
> provides not only
> > 2-shortest paths but also for k-shortest paths in a mesh network.
> >
> > You can find , specifically for 2-shortest paths, details in here;
> > J.W. Suurballe, R.E.Tarjan, "A Quick Method for Finding 
> Shortest Pairs of
> > Disjoint Paths", Networks, Vol. 14, 1984 pp 325-336.
> >
> > A generalized version of this algorithm for k-shortest 
> paths can be found
> > here though I find it difficult to understand
> > J.W.Suurballe, "Disjoint Paths in a Network", Networks, 
> Vol. 4., 1974,
> > pp125-145.
> >
> > Some other work is also done for k-shortest paths by Ramesh 
> Bhandari (He has
> > published a book and provided reference in a previous mail 
> on this list),
> > Eppstein (UC,Berkely), Prof Grover at University of Alberta 
> (also TRLabs).
> > Marali K and T.V.Laksham work has references to the above 
> work as well.
> >
> > Hope this answers your questions.
> >
> > Manohar
> >
> > ----- Original Message -----
> > From: "Wushao Wen" <[email-masked]>
> > To: <[email-masked]>
> > Sent: Sunday, January 21, 2001 8:09 PM