Browse Prior Art Database

Algorithm for Random Selection of Shortest Path

IP.com Disclosure Number: IPCOM000037025D
Original Publication Date: 1989-Nov-01
Included in the Prior Art Database: 2005-Jan-29
Document File: 3 page(s) / 20K

Publishing Venue

IBM

Related People

Ahmadi, H: AUTHOR [+3]

Abstract

Many networks, including communications networks, can be modelled as weighted graphs [1]; the weights may represent cost, expected delay or expected reliability of the links in the network. It is often necessary to find the shortest path between two nodes in such graphs, for example, to find suitable paths over which to route messages in a communications network. Examples of shortest-path routing in networks can be found in [2-4] while [5] provides additional motivations for its use. In such networks it is desirable to balance the load on the links of the network whenever this is consistent with the primary requirement of routing over the shortest available path. In some architectures, shortest paths are chosen asynchronously and independently many times.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 54% of the total text.

Page 1 of 3

Algorithm for Random Selection of Shortest Path

Many networks, including communications networks, can be modelled as weighted graphs [1]; the weights may represent cost, expected delay or expected reliability of the links in the network. It is often necessary to find the shortest path between two nodes in such graphs, for example, to find suitable paths over which to route messages in a communications network. Examples of shortest-path routing in networks can be found in [2-4] while [5] provides additional motivations for its use. In such networks it is desirable to balance the load on the links of the network whenever this is consistent with the primary requirement of routing over the shortest available path. In some architectures, shortest paths are chosen asynchronously and independently many times. Thus, we are led to the problem of finding an algorithm to determine the shortest path in a weighted graph which chooses each possible shortest path between a pair of nodes with equal probability.

We give here an algorithm for solving that problem. The algorithm computes, using a randomized Dijkstra shortest-path algorithm [1], a probability distribution for selecting among possible predecessors in a shortest path. Choosing predecessors according to this probability distribution results in all possible shortest paths having equal probability. The first two steps of the algorithm are, with the exception of the computation of Node Path Numbers for each node, identical to Dijkstra's algorithm to find all possible shortest paths between the source and destination. In the third step we compute, for each node in the graph, a probability distribution for selecting its predecessor in the shortest path between the source and destination. Finally, whenever a shortest path between the source and destination is required, we select a path, starting from the destination, choosing predecessors according to the above probability distribution.

ALGORITHM: Let G be a graph with N+1 nodes labeled (0,1,..., N) and with positive link weights wij = 0 &ij& N. By convention we assume B if nodes i and j are not directly connected. For simplicity, let 0 be the source and N the destination.

Notation:

P is the set of labeled nodes.

d(j) is th...