Original optimal method to solve the all-pairs shortest path problem: Dhouib-matrix-ALL-SPP  

作　　者：Souhail Dhouib 

机构地区：[1]Department of Industrial Management,Higher Institute of Industrial Management of Sfax,The University of Sfax,Sfax,BP 11693029,Tunisia

出　　处：《Data Science and Management》2024年第3期206-217,共12页数据科学与管理（英文）

摘　　要：The All-pairs shortest path problem(ALL-SPP)aims to find the shortest path joining all the vertices in a given graph.This study proposed a new optimal method,Dhouib-matrix-ALL-SPP(DM-ALL-SPP)to solve the ALL-SPP based on column-row navigation through the adjacency matrix.DM-ALL-SPP is designed to generate in a single execution the shortest path with details among all-pairs of vertices for a graph with positive and negative weighted edges.Even for graphs with a negative cycle,DM-ALL-SPP reported a negative cycle.In addition,DM-ALL-SPP continues to work for directed,undirected and mixed graphs.Furthermore,it is characterized by two phases:the first phase consists of adding by column repeated(n)iterations(where n is the number of vertices),and the second phase resides in adding by row executed in the worst case(n∗log(n))iterations.The first phase,focused on improving the elements of each column by adding their values to each row and modifying them with the smallest value.The second phase is emphasized by rows only for the elements modified in the first phase.Different instances from the literature were used to test the performance of the proposed DM-ALL-SPP method,which was developed using the Python programming language and the results were compared to those obtained by the Floyd-Warshall algorithm.

关 键 词：Artificial intelligence Operations research Combinatorial optimization Graph theory Network model All-pairs shortest paths problem Dhouib-matrix Intelligent networks 

分 类 号：O15[理学—数学]