Finding Simple Shortest-Paths via Centroids

Instance-Optimality of Bidirectional Dijkstra on Simple Graphs

We study the shortest-path problem on graphs with positive real-valued edge weights. Given a source vertex $s$ and a target vertex $t$, the goal is to calculate the length of the shortest path from $s$ to $t$. We are particularly interested in instances that can be solved in sublinear time. Recently, Haeupler, Hlad\'ik, Rozho\v{n}, Tarjan, and T\v{e}tek proved that (a version of) the bidirectional Dijkstra's algorithm is instance-optimal on positively weighted multigraphs, both directed and undirected, considering the number of vertices and edges queried by the algorithm. However, multigraphs are not the canonical setting for the shortest-path problem. The problem is typically formulated on simple graphs without loops and parallel edges. They therefore left as an open problem whether bidirectional Dijkstra remains instance-optimal on simple weighted graphs. We answer this question, but for simple graphs, the answer is more complex, depending on the setting. We show that bidirectional Dijkstra is still instance-optimal on simple undirected weighted graphs under the order-oblivious model, where incident edges are given in a random order. In contrast, under the order-dependent model, where incident edges have a given order, we show that bidirectional Dijkstra is not instance-optimal. For simple directed weighted graphs, we show that bidirectional Dijkstra is not instance-optimal under either the order-oblivious or the order-dependent model, being off by a factor of $\Theta(m/n)$ in both cases. We further show that no algorithm can have instance-optimality ratio $o(m/n)$ under the order-dependent model, or under the order-oblivious model when $m=O(n\sqrt{n})$. On the positive side, the above results imply that bidirectional Dijkstra is instance-optimal up to logarithmic factors on all sparse directed and undirected graphs satisfying $m/n=\log^{O(1)} n$.

Second shortest simple paths in directed graphs: a crossing decomposition and a span-adaptive exact algorithm

A novel approach for constructing a minimum spanning tree

The spanning tree of a graph is obtained when all vertices of a graph are connected in such a way that no cycle is formed. This work proposes a new algorithm that, at each round, selects a maximal independent set of vertices (an inclusion-maximal, not necessarily maximum-cardinality, set of pairwise non-adjacent vertices) and attaches to every vertex of that set its cheapest cycle-safe incident edge to find a minimum spanning tree of any weighted graph. The procedure organizes safe-edge selections into batches indexed by maximal independent sets; its number of such batching rounds depends on the maximal independent sets selected, and this notion of a round is not directly comparable to a single iteration of Prim's or Kruskal's algorithm without further definition. Using the classical cut property, we prove that the procedure always produces a minimum spanning tree of a connected graph. If r denotes the number of independent-set rounds, a straightforward sequential implementation has worst-case running time O(r(n+m)+m log m). We do not claim, and this paper does not prove, that the number of rounds is minimized over all possible choices of maximal independent sets, nor that the resulting sequential running time improves on the classical O(m log n) bounds. This work may be useful for large weighted networks such as communication networks, wiring connections, and transportation networks.

Efficient generation of networks with minimal average shortest-path distance

This work considers the problem of finding, for a given degree sequence, the network structure displaying the smallest possible average shortest-path length and proposes a fast algorithm to construct approximate solutions to such a degree-constrained distance-minimization problem.

Single Source Shortest Paths in Randomized Two-Dimensional Mesh Networks

The Single Source Shortest Path (SSSP) problem focuses on finding the shortest paths from a source vertex to all other vertices in a graph. This problem is crucial in various domains, including transportation, telecommunications and urban planning. Although Dijkstra's algorithm is effective for solving the SSSP in general cases, in some special cases, such as two-dimensional mesh networks (2DMN), its performance is not satisfactory. To address this limitation, this paper presents an improved approach, i.e., the row-by-row dynamic programming (RRDP) algorithm, which is specifically optimized for 2DMNs and can significantly reduce computation times, although in worst case the complexity of RRDP is higher than Dijkstra's algorithm. We tested the RRDP algorithm against the traditional Dijkstra's algorithm using the same 2DMN instances, and found that RRDP runs much faster than Dijkstra's algorithm on most instances. This innovation offers new insights and practical solutions for improving path planning algorithms in grid network environments.

Evaluating the Influence of Graph Density on the Efficiency of Shortest Path Algorithms Using Different Data Structures

This paper presents a comparative analysis of two variants of a classical algorithm for finding the shortest path in a connected graph. The first variant uses an adjacency matrix (AM) to verify the existence of an edge (arc) between two vertices, while the second variant performs the same verification using an adjacency list (AL). The objective of this study is to examine how graph density affects the performance of the two algorithmic modifications depending on the data structure used. A total of 95 graphs were analyzed, grouped into five sets from 100 to 500 in increments of 100. For each group, 19 graphs were generated with densities ranging from 5% to 95% in increments of 5%. The methodology includes analyzing the number of iterations, assignments, and comparisons executed by the algorithms for all graphs. The initial hypothesis assumed that the total number of operations would always be lower when using an AL instead of an adjacency matrix, regardless of graph density. The results demonstrate that this assumption is incorrect: for densities above 82%, the total number of operations is lower when using an adjacency matrix, whereas the AL is more efficient for densities below 82%, with its efficiency increasing as density decreases. These findings are particularly important for mobile technologies, as they support the design of more efficient pathfinding solutions that optimize performance and energy consumption in mobile applications.