A 2-PHASE SHORTEST-PATH ALGORITHM FOR NETWORKS WITH NODE COORDINATES

Jens Lysgaard

doi:10.1016/0377-2217(94)00152-3

A 2-PHASE SHORTEST-PATH ALGORITHM FOR NETWORKS WITH NODE COORDINATES

1995-12-01

9

PRE

AI

J

Jens Lysgaard *

DOI：10.1016/0377-2217(94)00152-3

原文链接

原文求助

摘要

En 中文

This paper presents a new algorithm for finding the shortest path from a source to a single sink in a network, in which the location in the plane of each node is known. The algorithm consists of two phases. In the first phase a heuristic solution to the shortest path problem is found. In the second phase the upper bound provided by the heuristic solution is utilized in a modification of a standard shortest path algorithm. Estimates based on computational tests show that on average the computation time of the presented algorithm is on the order of 40-60% of the computation time required if the information on node locations is not utilized.

Keyword:

OPTIMIZATION

HEURISTICS

NETWORK PROGRAMMING

A 2-PHASE SHORTEST-PATH ALGORITHM FOR NETWORKS WITH NODE COORDINATES

摘要

AI总结

期刊

机构

引用论文