Search engine for discovering works of Art, research articles, and books related to Art and Culture
Javascript must be enabled to continue!
Parallel Bidirectional Dijkstra's Shortest Path Algorithm
View through CrossRef
This paper deals with Dijkstra's shortest path algorithm and with the possibilities of speeding-up this algorithm. This algorithm is a breadth-first-search algorithm. The search spreads circularly around the source node in order to find the shortest path from the source node to other nodes. Each following iteration is based on the results of the previous iteration, therefore parallelization of such an algorithm is complicated. The parallel Dijkstra algorithm, proposed in this paper, is based on the bidirectional Dijkstra algorithm and popular multicore technology. Such a technology enables to create a parallel algorithm based on the shared memory and most of the time for data synchronization thereby is saved. The proposed algorithm has been tested using the real road network data. The proposed parallel algorithm is almost 3 times faster than the standard Dijkstra algorithm.
Title: Parallel Bidirectional Dijkstra's Shortest Path Algorithm
Description:
This paper deals with Dijkstra's shortest path algorithm and with the possibilities of speeding-up this algorithm.
This algorithm is a breadth-first-search algorithm.
The search spreads circularly around the source node in order to find the shortest path from the source node to other nodes.
Each following iteration is based on the results of the previous iteration, therefore parallelization of such an algorithm is complicated.
The parallel Dijkstra algorithm, proposed in this paper, is based on the bidirectional Dijkstra algorithm and popular multicore technology.
Such a technology enables to create a parallel algorithm based on the shared memory and most of the time for data synchronization thereby is saved.
The proposed algorithm has been tested using the real road network data.
The proposed parallel algorithm is almost 3 times faster than the standard Dijkstra algorithm.
Related Results
Dijkstra and Bidirectional Dijkstra on Determining Evacuation Routes
Dijkstra and Bidirectional Dijkstra on Determining Evacuation Routes
Abstract
Determination of the best path or often called the shortest path finding is a method that has many benefits and can be applied in various cases and fields o...
ENHANCING NETWORK PERFORMANCE LOAD BALANCING IN CYBER CAFE NETWORKS WITH DIJKSTRA ALGORITHM ON MIKROTIK
ENHANCING NETWORK PERFORMANCE LOAD BALANCING IN CYBER CAFE NETWORKS WITH DIJKSTRA ALGORITHM ON MIKROTIK
The internet has become a fundamental necessity in various activities today. Stream Cyber Cafe, as an internet service provider, faces the challenge of maintaining network quality ...
Implementation of the A Star Heuristic Search Algorithm in Determining the Shortest Path
Implementation of the A Star Heuristic Search Algorithm in Determining the Shortest Path
Finding the shortest path in a graph can be applied to various fields of shortest distance costs in routes, computer games, robotics or navigation. This study implements the A star...
Parallelizing Bidirectional A* Algorithm
Parallelizing Bidirectional A* Algorithm
Dijkstra’s algorithm is one of the simplest shortest path finding algorithm. A star(A*) algorithm is a variation of the shortest path first Dijkstra’s algorithm and is very commonl...
Implementation of Shortest Path Finding using Dijkstra’s Algorithm
Implementation of Shortest Path Finding using Dijkstra’s Algorithm
Dijkstra's algorithm is one of the algorithms that can be used in the shortest path determination process. Therefore, this research aims to create a simulation to implement how Dij...
An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation
An Extended Dijkstra's Algorithm for Calculating Alternative Routes for Evacuee Agents in Disaster Simulation
This paper proposes an extended Dijkstra's algorithm for calculating alternative routes for evacuee agents in a disaster simulation system. In a disaster simulation, evacuee agents...
The multi-point delivery problem: Shortest Path Algorithm for Real Roads Network using Dijkstra
The multi-point delivery problem: Shortest Path Algorithm for Real Roads Network using Dijkstra
Abstract
The Multi-point Delivery problem is a Vehicle Routing problem (VRP) in which the vehicle has single point as start and end point and must visit a set of poi...
Shortest paths avoiding forbidden subpaths
Shortest paths avoiding forbidden subpaths
AbstractWe study a variant of the shortest path problem in graphs: given a weighted graph Gand vertices sand t, and given a set Xof forbidden paths in G, find a shortest s‐ tpath P...