Time-dependent Dijkstra’s algorithm under bipolar neutrosophic fuzzy environment

Article type: Research Article

Authors: Çakır, Esra^{a; *} | Ulukan, Ziya^a | Acarman, Tankut^b

Affiliations: [a] Department of Industrial Engineering, GalatasarayUniversity, Ortakoy/Istanbul, Turkey | [b] Department of Computer Engineering, GalatasarayUniversity, Ortakoy/Istanbul, Turkey

Correspondence: [*] Corresponding author. E. Çakır. E-mail: [email protected].

Abstract: Determining the shortest path and calculating the shortest travel time of complex networks are important for transportation problems. Numerous approaches have been developed to search shortest path on graphs, and one of the well-known is the Dijkstra’s label correcting algorithm. Dijkstra’s approach is capable of determining shortest path of directed or undirected graph with non-negative weighted arcs. To handle with uncertainty in real-life, the Dijkstra’s algorithm should be adapted to fuzzy environment. The weight of arc -which is the vague travel time between two nodes- can be expressed in bipolar neutrosophic fuzzy sets containing positive and negative statements. In addition, the weights of arcs in bipolar neutrosophic fuzzy graphs can be affected by time. This study proposes the extended Dijkstra’s algorithm to search the shortest path and calculate the shortest travel time on a single source time-dependent network of bipolar neutrosophic fuzzy weighted arcs. The proposed approach is illustrated, and the results demonstrate the validity of the extended algorithm. This article is intended to guide future shortest path algorithms on time-dependent fuzzy graphs.

Keywords: Graph theory, Dijkstra’s algorithm, time-dependent shortest path problem, shortest travel time, fuzzy set theory, bipolar neutrosophic fuzzy number

DOI: 10.3233/JIFS-219188

Journal: Journal of Intelligent & Fuzzy Systems, vol. 42, no. 1, pp. 227-236, 2022