Analysis of the shortest path problem in network graphs

الملخص EN

The shortest path problem plays an important role in several practical applications both as standalone models and as sub-problems in more complex problem settings.

The shortest path is commonly used in network applications where it is required to send a message from a source node to a destination node.

In this work, two approaches for finding the shortest path are analyzed.

The first approach is based on Dijkstra algorithm while the second is based on the genetic algorithm.

The two approaches are applied on network graphs with different number of links as a test-bed.

If the number of links increases, the number of paths increases in a non-linear form; and therefore the execution time also increases.

The performance of the two approaches is evaluated and compared.

The comparison takes into account the overall time consumed in finding the shortest path.

From the point of view of the computational complexity, the first approach is adopted and modified.

The modification involves representing the network graph in a tree structure.

The tree root represents the source node while the leaves (or most of the leaves) represent the destination node.

Moreover, a parallel algorithm is proposed to exploit parallelism in finding the shortest path.

The parallel algorithm schedules and distributes the set of requests on more than one processor.

This reduces the time consumed in finding the shortest path.

Because the network topology is fixed, all the different paths among the network nodes can be generated automatically and stored in a database before the running time.

That database can be partitioned and searched in parallel by more than one processor to reduce the search time.

The overall execution time, the speedup and the average processors' utilization are improved by applying the proposed parallel scheduling algorithm to find the shortest path.

Generally speaking, exploiting parallelism and data partitioning to find the shortest path are promising.

This is also important for those network graphs with large number of nodes and links.