A hybrid single-source shortest path algorithm

Arslan, Hilal
Manguoğlu, Murat
The single-source shortest path problem arises in many applications, such as roads, social applications, and computer networks. Finding the shortest path is challenging, especially for graphs that contain a large number of vertices and edges. In this work, we propose a novel hybrid method that first sparsifies a given graph by removing most edges that cannot form the shortest path tree and then applies a classical shortest path algorithm to the sparser graph. Removing all the edges that cannot form the shortest path tree would be expensive since it is equivalent to solving the original problem. Therefore, we propose an iterative bioinspired algorithm, namely the Physarum algorithm, as the first stage to sparsify the graph. We prove that the resulting sparser graph always contains the shortest path tree of the original graph. Next, a state-of-the-art algorithm such as Dijkstra's is applied to find the single-source shortest path on the resulting graph. The proposed method is therefore a two-stage hybrid algorithm and it computes the single-source shortest path exactly. We compare the accuracy and solution time of the proposed hybrid method against state-of-the-art implementation of Dijkstra's algorithm and the BFS algorithm on directed weighted and unweighted graphs, respectively, as a baseline. The results show that the proposed hybrid method achieves a significant speed improvement compared to the baseline.


Adaptive mean-shift for automated multi object tracking
Beyan, C.; Temizel, Alptekin (2012-01-01)
Mean-shift tracking plays an important role in computer vision applications because of its robustness, ease of implementation and computational efficiency. In this study, a fully automatic multiple-object tracker based on mean-shift algorithm is presented. Foreground is extracted using a mixture of Gaussian followed by shadow and noise removal to initialise the object trackers and also used as a kernel mask to make the system more efficient by decreasing the search area and the number of iterations to conve...
A Hierarchical Partitioning Strategy for an Efficient Parallelization of the Multilevel Fast Multipole Algorithm
Ergül, Özgür Salih (Institute of Electrical and Electronics Engineers (IEEE), 2009-06-01)
We present a novel hierarchical partitioning strategy for the efficient parallelization of the multilevel fast multipole algorithm (MLFMA) on distributed-memory architectures to solve large-scale problems in electromagnetics. Unlike previous parallelization techniques, the tree structure of MLFMA is distributed among processors by partitioning both clusters and samples of fields at each level. Due to the improved load-balancing, the hierarchical strategy offers a higher parallelization efficiency than previ...
A low-order nonlinear amplifier model with distributed delay terms
YÜZER, AHMET HAYRETTİN; Demir, Şimşek (The Scientific and Technological Research Council of Turkey, 2014-01-01)
In this paper, a novel behavioral modeling technique for the characterization of memory effects of amplifiers is proposed. This characterization utilizes asymmetric intermodulation distortion (IMD)components, which are the result of a 2-tone excitation of a nonlinear amplifier. These asymmetric IMD components are represented basically by a power series, where each term in the series has its own time delay term. These time delay terms successfully justify the presence of asymmetry in the intermodulation comp...
Minimum concave cost multicommodity network design
Bazlamaçcı, Cüneyt Fehmi (Springer Science and Business Media LLC, 2007-12-01)
The minimum concave cost multicommodity network design problem (MCMNDP) arises in many application areas, such as transportation planning, energy distribution systems and especially in the design of both packet and circuit switching backbone networks. Exact concave cost optimization algorithms have been developed but they are applicable only if the network size is small. Therefore, MCMNDP is usually solved using non-exact iterative methods. In this paper, such heuristic techniques proposed within the contex...
A Modular Real-Time Fieldbus Architecture for Mobile Robotic Platforms
Saranlı, Uluç; Oeztuerk, M. Cihan (Institute of Electrical and Electronics Engineers (IEEE), 2011-03-01)
The design and construction of complex and reconfigurable embedded systems such as small autonomous mobile robots is a challenging task that involves the selection, interfacing, and programming of a large number of sensors and actuators. Facilitating this tedious process requires modularity and extensibility both in hardware and software components. In this paper, we introduce the universal robot bus (URB), a real-time fieldbus architecture that facilitates rapid integration of heterogeneous sensor and actu...
Citation Formats
H. Arslan and M. Manguoğlu, “A hybrid single-source shortest path algorithm,” TURKISH JOURNAL OF ELECTRICAL ENGINEERING AND COMPUTER SCIENCES, pp. 2636–2647, 2019, Accessed: 00, 2020. [Online]. Available: https://hdl.handle.net/11511/48503.