Shortest Path Search Method on a Graph with Cycles

This paper introduces a new shortest path algorithm based on the adjacency matrix representation of graphs. The algorithm searches for the shortest path between two certain vertices in the graph. The distinctive feature of the algorithm is that it works with loops and with negative weights. The algorithm divides the adjacency matrix into smaller submatrices for concurrent processing across multiple processors or threads. Experimental results on large graphs demonstrate significant speedup compared to sequential algorithms, with scalability analysis showcasing effective parallel resource utilization. The algorithm offers an efficient solution for computing shortest paths in large graphs, with potential applications in network routing and social network analysis.