Research on the shortest path problem of single source based on Q-learning

Zhehong Zhou; Bo Qu; Yuxin Zhai

doi:10.1117/12.3026831

27 March 2024 Research on the shortest path problem of single source based on Q-learning

Zhehong Zhou, Bo Qu, Yuxin Zhai

Proceedings Volume 13105, International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2023); 131053L (2024) https://doi.org/10.1117/12.3026831
Event: 3rd International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2023), 2023, Qingdao, China

Abstract

In the field of algorithm research, the problem of single-source shortest path has been discussed for a long time. In this paper, the problem of single source shortest path based on Q-learning is studied. Q-learning is a reinforcement learning algorithm that iterates to update the Q value of each state-action pair to determine the optimal path. When solving the single-source shortest path problem, each node in the graph is regarded as a state, and the edge between each node as an action. By using the Q-learning algorithm, we can find the optimal strategy, that is, to minimize the total cost from the starting point to the end point, and then find the shortest path. This paper introduces the implementation process of Q-learning algorithm, including initializing Q-table, selecting action, executing action, updating Q-table and so on. Finally, the effectiveness and feasibility of Q-learning algorithm are verified by experiments.

(2024) Published by SPIE. Downloading of the abstract is permitted for personal use only.

Citation Download Citation

Zhehong Zhou, Bo Qu, and Yuxin Zhai "Research on the shortest path problem of single source based on Q-learning", Proc. SPIE 13105, International Conference on Computer Graphics, Artificial Intelligence, and Data Processing (ICCAID 2023), 131053L (27 March 2024); https://doi.org/10.1117/12.3026831

ACCESS THE FULL ARTICLE

INSTITUTIONAL
Select your institution to access the SPIE Digital Library.

SELECT YOUR INSTITUTION

PERSONAL
Sign in with your SPIE account to access your personal subscriptions or to use specific features such as save to my library, sign up for alerts, save searches, etc.

PERSONAL SIGN IN

No SPIE Account? Create one

PURCHASE THIS CONTENT

SUBSCRIBE TO DIGITAL LIBRARY

50 downloads per 1-year subscription

Members: $195

Non-members: $335 ADD TO CART

25 downloads per 1 - year subscription

Members: $145

Non-members: $250 ADD TO CART

PURCHASE SINGLE ARTICLE

Includes PDF, HTML & Video, when available