On the Average Path Length of <I>O</I>(log <I>N</I>) in the Shortest Path Problem

GU Qian Ping; Tadao TAKAOKA

On the Average Path Length of O(log N) in the Shortest Path Problem

GU Qian Ping, Tadao TAKAOKA

Full Text Views

0

Cite this

Summary :

The shortest path from some vertex v to some other vertex w in edge weighted graph G(V, E, W) is the path from v to w with the minimum distance. Shortest path problem is defined to be the problem of finding the shortest path in G(V, E, W). In this paper a different version of shortest path problem is considered. The length of a path is defined to be the number of edges in the path here. The problem considered in this paper is the average length of the shortest paths in G(V, E, W) with non-negative edge distances. It is proved that the upper bound of the average length of a shortest path in G(V, E, W) is O(log N) when G(V, E, W) is a complete graph with N vertices and the distances associated to the edges in G are identically distributed on [0, 1] mutually independent random variables. A concept called shortest path spanning tree that is used in proving the upper bound is also given. Combining with an appropiate data structure, the upper bound proved in this paper implies that there is a shortest path enquiry system with response time O(log N) at the cost of O(N²) space requirement.

Publication: IEICE TRANSACTIONS on transactions Vol.E70-E No.11 pp.1155-1158

Publication Date: 1987/11/25

Publicized

Online ISSN

DOI

Type of Manuscript: PAPER

Category: Algorithm and Computational Complexity

Authors

GU Qian Ping
Tadao TAKAOKA

Keyword

Cite this

Copy

GU Qian Ping, Tadao TAKAOKA, "On the Average Path Length of O(log N) in the Shortest Path Problem" in IEICE TRANSACTIONS on transactions, vol. E70-E, no. 11, pp. 1155-1158, November 1987, doi: .
Abstract: The shortest path from some vertex v to some other vertex w in edge weighted graph G(V, E, W) is the path from v to w with the minimum distance. Shortest path problem is defined to be the problem of finding the shortest path in G(V, E, W). In this paper a different version of shortest path problem is considered. The length of a path is defined to be the number of edges in the path here. The problem considered in this paper is the average length of the shortest paths in G(V, E, W) with non-negative edge distances. It is proved that the upper bound of the average length of a shortest path in G(V, E, W) is O(log N) when G(V, E, W) is a complete graph with N vertices and the distances associated to the edges in G are identically distributed on [0, 1] mutually independent random variables. A concept called shortest path spanning tree that is used in proving the upper bound is also given. Combining with an appropiate data structure, the upper bound proved in this paper implies that there is a shortest path enquiry system with response time O(log N) at the cost of O(N²) space requirement.
URL: https://global.ieice.org/en_transactions/transactions/10.1587/e70-e_11_1155/_p

Copy

@ARTICLE{e70-e_11_1155,
author={GU Qian Ping, Tadao TAKAOKA, },
journal={IEICE TRANSACTIONS on transactions},
title={On the Average Path Length of O(log N) in the Shortest Path Problem},
year={1987},
volume={E70-E},
number={11},
pages={1155-1158},
abstract={The shortest path from some vertex v to some other vertex w in edge weighted graph G(V, E, W) is the path from v to w with the minimum distance. Shortest path problem is defined to be the problem of finding the shortest path in G(V, E, W). In this paper a different version of shortest path problem is considered. The length of a path is defined to be the number of edges in the path here. The problem considered in this paper is the average length of the shortest paths in G(V, E, W) with non-negative edge distances. It is proved that the upper bound of the average length of a shortest path in G(V, E, W) is O(log N) when G(V, E, W) is a complete graph with N vertices and the distances associated to the edges in G are identically distributed on [0, 1] mutually independent random variables. A concept called shortest path spanning tree that is used in proving the upper bound is also given. Combining with an appropiate data structure, the upper bound proved in this paper implies that there is a shortest path enquiry system with response time O(log N) at the cost of O(N²) space requirement.},
keywords={},
doi={},
ISSN={},
month={November},}

Copy

TY - JOUR
TI - On the Average Path Length of O(log N) in the Shortest Path Problem
T2 - IEICE TRANSACTIONS on transactions
SP - 1155
EP - 1158
AU - GU Qian Ping
AU - Tadao TAKAOKA
PY - 1987
DO -
JO - IEICE TRANSACTIONS on transactions
SN -
VL - E70-E
IS - 11
JA - IEICE TRANSACTIONS on transactions
Y1 - November 1987
AB - The shortest path from some vertex v to some other vertex w in edge weighted graph G(V, E, W) is the path from v to w with the minimum distance. Shortest path problem is defined to be the problem of finding the shortest path in G(V, E, W). In this paper a different version of shortest path problem is considered. The length of a path is defined to be the number of edges in the path here. The problem considered in this paper is the average length of the shortest paths in G(V, E, W) with non-negative edge distances. It is proved that the upper bound of the average length of a shortest path in G(V, E, W) is O(log N) when G(V, E, W) is a complete graph with N vertices and the distances associated to the edges in G are identically distributed on [0, 1] mutually independent random variables. A concept called shortest path spanning tree that is used in proving the upper bound is also given. Combining with an appropiate data structure, the upper bound proved in this paper implies that there is a shortest path enquiry system with response time O(log N) at the cost of O(N²) space requirement.
ER -