AI Article Synopsis
- The text discusses solving the shortest path problem in directed graphs using a mathematical technique involving matrix inversion based on an adjacency matrix.
- It introduces a parameter γ that, with a small value, helps to compute shortest path distances, and demonstrates this method's effectiveness even in cases where it isn't globally accurate.
- The approach is computationally efficient for dense graphs and is linked to a neural network solution for solving the all-pairs-shortest-path problem.
Article Abstract
Given a directed graph of nodes and edges connecting them, a common problem is to find the shortest path between any two nodes. Here we show that the shortest path distances can be found by a simple matrix inversion: if the edges are given by the adjacency matrix Aij, then with a suitably small value of γ, the shortest path distances are Dij=ceil(logγ[(I-γA)-1]ij).We derive several graph-theoretic bounds on the value of γ and explore its useful range with numerics on different graph types. Even when the distance function is not globally accurate across the entire graph, it still works locally to instruct pursuit of the shortest path. In this mode, it also extends to weighted graphs with positive edge weights. For a wide range of dense graphs, this distance function is computationally faster than the best available alternative. Finally, we show that this method leads naturally to a neural network solution of the all-pairs-shortest-path problem.
Download full-text PDF |
Source |
|---|---|
| http://dx.doi.org/10.1162/neco_a_01716 | DOI Listing |
Publication Analysis
Top Keywords
Similar Publications
Characterization of language abilities and semantic networks in very preterm children at school-age.
PLoS One
January 2025
Clinic of Neonatology, Department of Mother-Woman-Child, Lausanne University Hospital and University of Lausanne, Lausanne, Switzerland.
It has been widely assessed that very preterm children (<32 weeks gestational age) present language and memory impairments compared with full-term children. However, differences in their underlying semantic memory structure have not been studied yet. Nevertheless, the way concepts are learned and organized across development relates to children's capacities in retrieving and using information later.
View Article and Find Full Text PDFInvestigating the potential of diffusion tensor atlases to generate anisotropic clinical tumor volumes in glioblastoma patients.
Phys Imaging Radiat Oncol
January 2025
Aarhus University Hospital, Danish Centre for Particle Therapy, Palle Juul-Jensens Blvd. 25, 8200 Aarhus, Denmark.
Background And Purpose: Diffusion tensor imaging (DTI) has been proposed to guide the anisotropic expansion from gross tumor volume to clinical target volume (CTV), aiming to integrate known tumor spread patterns into the CTV. This study investigate the potential of using a DTI atlas as an alternative to patient-specific DTI for generating anisotropic CTVs.
Materials And Methods: The dataset consisted of twenty-eight newly diagnosed glioblastoma patients from a Danish national DTI protocol with post-operative T1-contrast and DTI imaging.
A Fuzzy Control Strategy for Multi-Goal Autonomous Robot Navigation.
Sensors (Basel)
January 2025
Department of Product & Systems Design Engineering, University of the Aegean, 84100 Syros, Greece.
This paper addresses the complex problem of multi-goal robot navigation, framed as an NP-hard traveling salesman problem (TSP), in environments with both static and dynamic obstacles. The proposed approach integrates a novel path planning algorithm based on the Bump-Surface concept to optimize the shortest collision-free path among static obstacles, while a Genetic Algorithm (GA) is employed to determine the optimal sequence of goal points. To manage static or dynamic obstacles, two fuzzy controllers are developed: one for real-time path tracking and another for dynamic obstacle avoidance.
View Article and Find Full Text PDFEnergy-Efficient Route Planning Method for Ships Based on Level Set.
Sensors (Basel)
January 2025
The Department of Aeronautical and Automotive Engineering, Loughborough University, Loughborough LE11 3RH, UK.
To reduce the fuel consumption of ships' oceanic voyages, this study incorporates the influence of ocean currents into the traditional level set algorithm and proposes a route planning algorithm capable of identifying energy-efficient routes in complex and variable sea conditions. The approach introduces the influence factor of ocean current to optimize routing in dynamically changing marie environments. First, models for the energy consumption of ships and flow fields are established.
View Article and Find Full Text PDFDeciphering allosteric mechanisms in KRAS activation: insights from GTP-induced conformational dynamics and interaction network reorganization.
RSC Adv
January 2025
College of Agriculture and Biological Science, Dali University Dali 671000 China
The conformational dynamics and activation mechanisms of KRAS proteins are of great importance for targeted cancer therapy. However, the detailed molecular mechanics of KRAS activation induced by GTP binding remains unclear. In this study, we systematically investigated how GTP/GDP exchange affects the thermodynamic and kinetic properties of KRAS and explored the activation mechanism using molecular dynamics (MD) simulations, Markov state models (MSMs), and neural relational inference (NRI) models.
View Article and Find Full Text PDFWant AI Summaries of new PubMed Abstracts delivered to your In-box?
Enter search terms and have AI summaries delivered each week - change queries or unsubscribe any time!