An optimal method for the Shortest Path Problem: The Dhouib-Matrix-SPP (DM-SPP)

Abstract

This paper introduces an optimal method entitled Dhouib-Matrix-SPP (DM-SPP) in order to solve the Shortest Path Problem with a complexity time of On+mwhere n and m are respectively the number of vertices and edges. DM-SPP is a rapid method, it can reduce reasonably the research time and consequently the running time as well as the energy consumption. It is composed of five simple steps repeated in (n-1) iterations and for more clarification a guided step-by-step application of the novel method DM-SPP is presented. Moreover, several examples are solved wherein a fully complete and random distribute graphs are analyzed with the variation of the number of vertices from 20 to 6000 and the number of edges from 49 to 17097565. DM-SPP is coded under Python programming language and all experimental results demonstrate that DM-SPP can rapidly generate the optimal short path. Furthermore, by comparing the complexity time required by DM-SPP to the time prerequisite by Dijkstra algorithm, it can be concluded that DM-SPP and Dijkstra are concurrent for small instances and for larger instances DM-SPP can easily outperform Dijkstra and especially for the case of incomplete undirected graphs which are more realistic in the real-world viewing that all graphs are really not complete. The performance of DM-SPP is statistically confirmed with the Mann–Whitney U nonparametric test Further research trends will focus on the test of DM-SPP for the uncertain Shortest Path problem and the resolution of the autonomous mobile robot path planning problem.

Keywords

• Network flows
• Routing
• Distribution
• Distance function
• Dijkstra algorithm
• Polynomial-time algorithm