Results 1 to 10 of about 484,854 (185)
Random assignment and shortest path problems [PDF]
Discrete Mathematics & Theoretical Computer Science, 2006 We explore a similarity between the $n$ by $n$ random assignment problem and the random shortest path problem on the complete graph on $n+1$ vertices. This similarity is a consequence of the proof of the Parisi formula for the assignment problem given by
Johan Wästlund
doaj +5 more sources
Neutrosophic Shortest Path Problem [PDF]
Neutrosophic Sets and Systems, 2018 Neutrosophic set theory provides a new tool to handle the uncertainties in shortest path problem (SPP). This paper introduces the SPP from a source node to a destination node on a neutrosophic graph in which a positive neutrosophic number is assigned to ...
Ranjan Kumar +4 more
doaj +3 more sources
A lower bound for the shortest path problem [PDF]
Proceedings 15th Annual IEEE Conference on Computational Complexity, 2002 AbstractWe show that the shortest path problem cannot be solved in o(logn) time on an unbounded fan-in PRAM without bit operations using poly(n) processors, even when the bit-lengths of the weights on the edges are restricted to be of size O(log3n). This shows that the matrix-based repeated squaring algorithm for the shortest path problem is optimal in
K. Mulmuley, P. Shah
openalex +4 more sources
Shortest Path Problems on a Polyhedral Surface [PDF]
Algorithmica, 2009 We develop algorithms to compute edge sequences, Voronoi diagrams, shortest path maps, the Fréchet distance, and the diameter for a polyhedral surface. Distances on the surface are measured either by the length of a Euclidean shortest path or by link distance. Our main result is a linear-factor speedup for computing all shortest path edge sequences on
Atlas F. Cook, Carola Wenk
openalex +6 more sources
, 2007 Cet article constitue un etat de l’art sur les problemes de plus courts chemins pour lesquels il existe des elements d’incertitude et d’indetermination sur les valeurs des arcs. Deux modeles d’incertitude sont distingues : celui dit par intervalle et celui dit par scenarios.
Virginie Gabrel, Cécile Murat
+7 more sources
Shortest Path from Bandar Tun Razak to Berjaya Times Square using Dijkstra Algorithm
Journal of Computing Research and Innovation, 2020 The shortest path is an issue that involves the route from one point (nodes) to another. It is to find a path with a minimum travelling time. Nowadays, traffic problems have affected many transport users especially in Kuala Lumpur area.
Nur Syuhada Muhammat Pazil +2 more
doaj +5 more sources
An Effective Genetic Algorithm for Solving the Clustered Shortest-Path Tree Problem
IEEE Access, 2021 The clustered shortest-path tree problem (CluSPTP) is an extension of the classical single-source shortest-path problem, in which, given a graph with the set of nodes partitioned into a predefined, mutually exclusive and exhaustive set of clusters, we ...
Ovidiu Cosma +2 more
doaj +1 more source
A Novel Method for Solving Multi-objective Shortest Path Problem in Respect of Probability Theory
Tehnički Glasnik, 2023 Transportation process or activity can be considered as a multi-objective problem reasonably. However, it is difficult to obtain an absolute shortest path with optimizing the multiple objectives at the same time by means of Pareto approach. In this paper,
Maosheng Zheng, Jie Yu
doaj +1 more source
A Pathfinding Problem for Fork-Join Directed Acyclic Graphs with Unknown Edge Length
Algorithms, 2021 In a previous paper by the author, a pathfinding problem for directed trees is studied under the following situation: each edge has a nonnegative integer length, but the length is unknown in advance and should be found by a procedure whose computational ...
Kunihiko Hiraishi
doaj +1 more source
TD-H2H: Shortest Path Query on Time-Dependent Graphs [PDF]
Jisuanji kexue yu tansuo, 2023 A shortest path query on road networks is a fundamental problem, which has been studied widely. Existing studies usually model road networks as a static graph and query the path with the shortest distance between given vertices.
LI Xinling, WANG Yishu, YUAN Ye, GU Xiang, WANG Guoren
doaj +1 more source