k-Fewest Turn and Shortest Path Algorithm based on Stroke Graph
Daisuke Yamamoto, Yuki Hiura, Yonghwan Kim · 2023
This paper proposes the k-fewest turn and shortest path (k-FTSP) algorithm to solve the problem of route search in web mapping systems. Conventional shortest path search has a problem in that the generated shortest path may include many right and/or left turns. Although the fewest turn path algorithm can find a path that minimizes the number of turns, the paths tend to become longer, which can be burdensome, particularly for pedestrians. There are several methods for generating routes based on both the number of turns and distance, but many of them are either approximation techniques or require a significant amount of time. This papaer proposed the k-FTSP algorithm to find the shortest path when k = 1, the path with the fewest turns when k = n, and intermediate and optimal paths based on both the path length and number of turns when 1 < k < n. These paths are not approximations but represent unique and exact solutions. This enables users to select their preferred routes among multiple options based on their preferences and requirements.