Jove
Visualize
Contact Us
JoVE
x logofacebook logolinkedin logoyoutube logo
ABOUT JoVE
OverviewLeadershipBlogJoVE Help Center
AUTHORS
Publishing ProcessEditorial BoardScope & PoliciesPeer ReviewFAQSubmit
LIBRARIANS
TestimonialsSubscriptionsAccessResourcesLibrary Advisory BoardFAQ
RESEARCH
JoVE JournalMethods CollectionsJoVE Encyclopedia of ExperimentsArchive
EDUCATION
JoVE CoreJoVE BusinessJoVE Science EducationJoVE Lab ManualFaculty Resource CenterFaculty Site
Terms & Conditions of Use
Privacy Policy
Policies

Related Experiment Videos

Dynamic algorithms for the shortest path routing problem: learning automata-based solutions.

Sudip Misra1, B John Oommen

  • 1School of Computer Science, Carleton University, Ottawa, ON, Canada. smisra_@scs.carleton.ca

IEEE Transactions on Systems, Man, and Cybernetics. Part B, Cybernetics : a Publication of the IEEE Systems, Man, and Cybernetics Society
|December 22, 2005
PubMed
Summary
This summary is machine-generated.

Related Concept Videos

You might also read

Related Articles

Articles linked to this work by shared authors, journal, and citation graph.

Sort by
Same author

COTiR: Molecular Communication Model for Synthetic Exosome-Based Tissue Regeneration.

IEEE transactions on nanobioscience·2023
Same author

Estimating Time Window to Administer Anti-Cytokine Therapeutic Drugs to COVID-19 Patients.

IEEE transactions on nanobioscience·2023
Same author

The Hierarchical Discrete Pursuit Learning Automaton: A Novel Scheme With Fast Convergence and Epsilon-Optimality.

IEEE transactions on neural networks and learning systems·2023
Same author

i-Sheet: A Low-Cost Bedsheet Sensor for Remote Diagnosis of Isolated Individuals.

IEEE sensors journal·2023
Same author

VIVID: <i>In Vivo</i> End-to-End Molecular Communication Model for COVID-19.

IEEE transactions on molecular, biological, and multi-scale communications·2022
Same author

Persistent Service Provisioning Framework for IoMT Based Emergency Mobile Healthcare Units.

IEEE journal of biomedical and health informatics·2022
Same journal

Strategic Ability Updating in Concurrent Games by Coalitional Commitment.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2015
Same journal

Meta-Analysis of the First Facial Expression Recognition Challenge.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Adjustable model-based fusion method for multispectral and panchromatic images.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Face Feature Weighted Fusion Based on Fuzzy Membership Degree for Video Face Recognition.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

A New Adaptive Fast Cellular Automaton Neighborhood Detection and Rule Identification Algorithm.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
Same journal

Human-arm-and-hand-dynamic model with variability analyses for a stylus-based haptic interface.

IEEE transactions on systems, man, and cybernetics. Part B, Cybernetics : a publication of the IEEE Systems, Man, and Cybernetics Society·2012
See all related articles

This study introduces a novel Learning Automaton-based algorithm for the dynamic single source shortest path problem in stochastic graphs. The efficient new method finds statistical shortest paths, outperforming existing algorithms in dynamic environments.

Area of Science:

  • Computer Science
  • Artificial Intelligence
  • Graph Theory

Background:

  • Dynamic single source shortest path (SSSP) problem is crucial in network analysis.
  • Stochastic graph topologies with continuous edge-weight updates pose significant computational challenges.
  • Existing algorithms often struggle with efficiency and convergence in dynamic, probabilistic environments.

Purpose of the Study:

  • To present the first Learning Automaton-based solution for the dynamic SSSP problem.
  • To develop an algorithm that efficiently finds statistical shortest paths in stochastic graphs.
  • To demonstrate superior performance compared to existing methods in dynamic edge-weight scenarios.

Main Methods:

  • Developed a Learning Automaton-based algorithm for dynamic SSSP.

Related Experiment Videos

  • Algorithm focuses on probing edges likely to be in the shortest path, minimizing probing of others.
  • Tested algorithm in stochastic environments with simultaneous edge-weight updates.

    • Main Results:

    • The proposed algorithm converges to the statistical shortest path tree in average graph topology.
    • It exhibits significantly higher efficiency than existing solutions in terms of processed nodes, scanned edges, and time per update.
    • The algorithm successfully handles continuous probabilistic updates in edge-weights.

    Conclusions:

    • Learning Automata provide an efficient solution for dynamic SSSP in stochastic graphs.
    • The algorithm's targeted probing strategy enhances performance and ensures convergence.
    • Applicable across diverse domains including transportation, telecommunications, and military systems.