Comparing the pathfinding algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and best first search for the paparazzi problem
No Thumbnail Available
Author (Corporation)
Publication date
2022
Typ of student thesis
Course of study
Collections
Type
04B - Conference paper
Editor (Corporation)
Supervisor
Parent work
Congress on Intelligent Systems. Proceedings of CIS 2021
Special issue
DOI of the original publication
Link
Series
Lecture Notes on Data Engineering and Communications Technologies
Series number
111
Volume
2
Issue / Number
Pages / Duration
561-576
Patent number
Publisher / Publishing institution
Springer
Place of publication / Event location
Singapore
Edition
Version
Programming language
Assignee
Practice partner / Client
Abstract
This paper aims to compare A*, Dijkstra, Bellmann-Ford, Floyd-Warshall, and best first search algorithms to solve a particular variant of the pathfinding problem based on the so-called paparazzi problem. This problem consists of a grid with different non-moving obstacles that lead to different traversing costs which are considered as minimization objective in a specific model. The performance of the algorithms that solve the paparazzi problem is compared in terms of computation time, the number of visited nodes, shortest path cost, and accuracy of finding the shortest path. The comparison shows that heuristic algorithms mostly provide the optimal path but with a shorter computation time.
Keywords
Subject (DDC)
330 - Wirtschaft
Event
2nd Congress on Intelligent Systems CIS 2021
Exhibition start date
Exhibition end date
Conference start date
Conference end date
Date of the last check
ISBN
978-981-16-9112-6
978-981-16-9113-3
978-981-16-9113-3
ISSN
Language
English
Created during FHNW affiliation
Yes
Strategic action fields FHNW
Publication status
Published
Review
Peer review of the complete publication
Open access category
Closed
License
Citation
JOHNER, Robert, Antonino LANAIA, Rolf DORNBERGER und Thomas HANNE, 2022. Comparing the pathfinding algorithms A*, Dijkstra’s, Bellman-Ford, Floyd-Warshall, and best first search for the paparazzi problem. In: Mukesh SARASWAT, Harish SHARMA, K. BALACHANDRAN, Joong Hoon KIM und Jagdish Chand BANSAL (Hrsg.), Congress on Intelligent Systems. Proceedings of CIS 2021. Singapore: Springer. 2022. S. 561–576. Lecture Notes on Data Engineering and Communications Technologies, 111. ISBN 978-981-16-9112-6. Verfügbar unter: https://irf.fhnw.ch/handle/11654/48193