20 papers · ranked by Valyu relevance
A. Kapanowski, Ł. Gałuszka
Python implementation of selected weighted graph algorithms is presented. The minimal graph interface is defined together with several classes implementing this interface. Graph nodes can be any hashable Python objects. Directed edges are instances of the Edge class. Graphs are instances of the Graph class. It is based…
Rhyd Lewis
This paper describes the shortest path problem in weighted graphs and examines the differences in efficiency that occur when using Dijkstra's algorithm with a Fibonacci heap, binary heap, and self-balancing binary tree. Using C++ implementations of these algorithm variants, we find that the fastest method is not always…
Vijay K. Garg
depend upon edge-relaxation where the cost of reaching a vertex from a source vertex is possibly decreased if that edge is used. We introduce a method which maintains lower bounds as well as upper bounds for reaching a vertex. This method enables one to find the optimal cost for multiple vertices in one iteration and…
Seifedine Kadry, Ayman Bahjat Abdallah, Chibli Joumaa
In this paper, we propose some amendment on Dijkstra's algorithm in order to optimize it by reducing the number of iterations. The main idea is to solve the problem where more than one node satisfies the condition of the second step in the traditional Dijkstra's algorithm. After application of the proposed…
Kornél Katona, Husam A. Neamah, Péter Korondi, David Cheneler + 1 more
'Stephen Monk'] Path planning creates the shortest path from the source to the destination based on sensory information obtained from the environment. Within path planning, obstacle avoidance is a crucial task in robotics, as the autonomous operation of robots needs to reach their destination without collisions.…
Zongchao Wei
At present, e-commerce drives the logistics industry to develop greatly, but at the same time, there is a huge demand in this field, such as lower cost and higher efficiency. Facing the needs of logistics management development, it needs the blessing of intelligent technology, which involves countless fields at…
Zhaodi Li, Dan Li
At present, the large amount of data generated by transportation and logistics in cities brings great difficulties to data management and operation. The purpose is to explore the applicability of WebGIS and expand the application of intelligent interactive urban traffic logistics management. An urban traffic logistics…
Kevin Y. Chen
Finding the shortest path between two points in a graph is a fundamental problem that has been well-studied over the past several decades. Shortest path algorithms are commonly applied to modern navigation systems, so our study aims to improve the efficiency of an existing algorithm on large-scale Euclidean networks.…
Guojun Nan, Zhuo Liu, Haibo Du, Wenwu Zhu + 2 more
'Fco Javier Rodríguez'] An improved Dijkstra algorithm based on adaptive resolution grid (ARG) is proposed to assist manual transmission line planning, shorten the construction period and achieve lower cost and higher efficiency of line selection. Firstly, the semantic segmentation network is used to change the remote…
Yunfeng Yao, Na He, Min Zhang
With the advent of the Internet of Everything era, multi-information integration, and development, technology has penetrated into all aspects of life, promoting the continuous progress of social development, and people's requirements for a happy life are getting higher and higher. In this, robots play an extremely…
Piyush Udhan, Akhilesh Ganeshkar, Poobigan Murugesan, Abhishek Raj Permani + 2 more
'Abhishek Raj Permani' 'Sameep Sanjeeva' 'Parth Deshpande'] Abstract—Traditional vehicle routing algorithms do not consider the changing nature of traffic. While implementations of Dijkstra's algorithm with varying weights exist, the weights are often changed after the outcome of algorithm is executed, which may not…
Wei-Chang Yeh
This paper proposes earliest and latest path algorithms based on binary weight allocation, assigning weights of 2(i-1) and 2(m-i) to the i-th arc in a network. While traditional shortest path algorithms optimize only distance, our approach leverages Binary-Addition-Tree ordering to efficiently identify…
Rudolph Pienaar, Christian Hasselgrove, Kiho Im, David Kennedy + 4 more
We present a description of a system that uses a compact binary representation to describe and trace sulci on a reconstructed human cortical surface, based on a set of human-generated targets. The inputs to the system were manually created on a training set of 20 normal subjects (11 females, 9 males) with ages 22 – 40…
Jing Xie, Qi Duan
Biological pathway analysis often requires identifying interventions that block reachability to an undesirable state, such as a disease-associated module, toxic byproduct, or adverse phenotype, while preserving reachability among essential biological functions. Motivated by this setting, we study the Reachability…
Haitao Wei, Shusheng Zhang, Xiaohui He
Accurate and fast path calculation is essential for applications such as vehicle navigation systems and transportation network routing. Although many shortest path algorithms for restricted search areas have been developed in the past ten years to speed up the efficiency of path query, the performance including the…
Pesho Ivanov, Benjamin Bichsel, Harun Mustafa, André Kahles + 2 more
We present an algorithm for the optimal alignment of sequences to genome graphs. It works by phrasing the edit distance minimization task as finding a shortest path on an implicit alignment graph. To find a shortest path, we instantiate the A^⋆^ paradigm with a novel domain-specific heuristic function that accounts for…
Simon Van den Eynde, Pieter Audenaert, Didier Colle, Mario Pickavet + 1 more
Many real-life problems boil down to a variant of the Minimum Steiner Tree Problem (STP). In telecommunications, Fiber-To-The-Home (FTTH) houses are clustered so they can be connected with fiber as cost-efficiently as possible. The cost calculation of a fiber installment can be formulated as a capacitated STP. Often…
Ragnar Groot Koerkamp, Pesho Ivanov
Sequence alignment has been at the core of computational biology for half a century. Still, it is an open problem to design a practical algorithm for exact alignment of a pair of related sequences in linear-like time (25). We solve exact global pairwise alignment with respect to edit distance by using the A shortest…
Lionel Zoubritzky, François-Xavier Coudert
We present here an open-source Julia library for the topological identification of crystalline materials, with algorithmic and computational improvements over the previously available software in the field, resulting in a speed increase of one order of magnitude. This new algorithm and implementation can therefore be…
Authors not listed
Identifying synthesis routes from knowledge graphs poses challenges beyond retrosynthesis, including path–finding artifacts and data issues. We introduce “SynGPS”, a novel algorithm that overcomes these limitations by identifying viable routes even with common artifacts. SynGPS can resolve nonsensical cycles…