Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Algorithm for Generating Longest/Shortest Paths Incrementally

IP.com Disclosure Number: IPCOM000108134D
Original Publication Date: 1992-Apr-01
Included in the Prior Art Database: 2005-Mar-22
Document File: 2 page(s) / 77K

Publishing Venue

IBM

Related People

Kundu, S: AUTHOR

Abstract

Disclosed is an algorithm that finds the next k longest or shortest paths of a directed acyclic graph on demand without computing all previous paths.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 52% of the total text.

Algorithm for Generating Longest/Shortest Paths Incrementally

       Disclosed  is  an algorithm that finds the next k longest
or shortest paths of a directed acyclic graph on demand without
computing all previous paths.

      The solution presented here is incremental. The basic steps are
as follows: Graph processing
1. Process the graph such that only edges have weights.
2. Create a pseudo input node and a pseudo output node.
3. Connect all external inputs to a pseudo input  node. If external
input is an edge, it emanates from pseudo node. If external input is
a node, create a directed edge from pseudo input node to this node
that has weight 0.  Likewise, all outputs converge on pseudo output
node.
Algorithm
1. Associate a list of length K with each node to generate K longest
(shortest) paths that contains cumulative weights as its value
elements.  These values are stored in non-decreasing order to find
the shortest paths and non-increasing order to find the longest
paths.
2. The pseudo input node has value (0, E, E, ...,  E)  where the
first value  of the list is 0 and all others are empty (E).
3.  Compute  the list of values at every node in a levelized rank
order using the following list merging technique:
Suppose a node has n sources.   Then obtain a list of n*K elements,
by adding the edge weight of each source edge with every value
element of its source node. Order the non-empty values according to
request (longest or shortest) and assign the top K elements of this
sorted list to the value list at the node being computed.  Memorize
the sources by creating pointers.  If there are fewer than K
non-empty  elements, then empty elements are placed at the bottom.
4.  Backward trace...