THE THREE MOST APPROPRIATE ALGORITHMS FOR CALCULATING SHORTEST PATHS IN TRANSPORT ROAD NETWORKS - THOSE DUE TO MOORE, D'ESOPO AND DIJKSTRA - ARE EXAMINED USING CPU TIMES ON FIVE REALISTIC NETWORKS AS CRITERIA. THEIR RELATIVE EFFICIENCIES ARE SHOWN TO DEPEND ON CERTAIN CHARACTERISTICS OF THE NETWORK. IN APPROXIMATE ORDER OF IMPORTANCE THESE ARE: THE NETWORK SIZE (IN TERMS OF THE NUMBER OF NODES, N NODES, AND/OR LINKS, N LINKS), THE MEAN LINK LENGTH D (IN TERMS OF THE NUMBER OF INTEGER UNITS), THE COEFFICIENT OF VARIATION OF THE LINK LENGTHS, THE SHAPE OF THE NETWORK AND THE RATIO OF LINKS TO NODES. QUANTITATIVE RULES COVERING THE FIRST TWO FACTORS HAVE BEEN DERIVED INDICATING THAT THE FASTEST ALGORITHM WILL BE: (1) DIJKSTRA FOR NETWORKS WHERE D/N NODES LESS THAN C1; (2) MOORE IF N NODES LESS THAN C2; (3) D'ESOPO UNDER ALL OTHER CONDITIONS. C1 AND C2 ARE PARAMETERS APPROXIMATELY 0.02 AND 75 RESPECTIVELY FOR FORTRAN IV PROGRAMS ON AN ICL 1906A; THESE VALUES ARE EXPECTED TO VARY FROM ONE COMPUTER INSTALLATION TO ANOTHER. QUALITATIVE GUIDELINES AS TO THE EFFECT OF THE OTHER THREE FACTORS ARE GIVEN. A NUMBER OF SUGGESTIONS ARE ALSO MADE FOR IMPROVED NETWORK DATA STRUCTURES AND FOR REDUCING THE SIZE OF THE NETWORK PRIOR TO CALCULATING SHORTEST PATHS. BOTH ARE APPLICABLE TO ANY OF THE BASIC ALGORITHMS CONSIDERED AND TAKEN TOGETHER, CAN REDUCE CPU TIMES BY UP TO 40%.(Author/publisher).
Samenvatting