Shortest paths on the Web as computing medium, in randomly generated maps

Abstract

When dealing with routes in maps, the shortest path is the commonest addressed problem, but the topology of the map affects the paths’ behavior in many ways. A study was conducted on random maps, by Monte Carlo simulation, in which the weights are uniformly distributed, in order to assess the impact of these conditions on the shortest paths. We provide a freely accessible webpage, where the user can insert the number of nodes, specify whether it is a directed or undirected graph, and the range of the distribution, to observe the influence of each parameter. We consider several goals: we offer the procedure computation, based on the well-known Dijkstra’s algorithm; we combine the PHP language with a numerical language (Fortran), with the gnuplot graphing utility; and we stress the suggestion of the Internet as a computing medium. The simulation runs on the webpage, thus needing no software installation or special power or matching operating system. This Web application is an example for many other problems, and is implemented on a Linux platform. The study draws attention both to the use of the Web for scientific computing, and to the convenience of this use in scientific publications. We advocate web-based computing in general, as it can use the same programs as classical computing, the programs being always the technical difficulty. In our technological era, this still scarcely explored approach also promotes the transfer of knowledge from academia to industry.