Design and implementation of shortest path algorithm for network of roads

Abstract EN

In this paper a new method programmed computerizing has been suggested which depends on converting the roads network to matrix and the representation of this matrix in adjacency matrix, that a number of rows is equal number of columns, where the degree of this matrix is equal for number of the edges plus one in (i) multiplied by number of the edges plus one in (j) of the roads network (graph).

The elements of This matrix will be either (1) that means existing edge of orientation in one direction connecting between two nodes continuous connection, or (0) and that means there is no edge of oriented connecting between two nodes.

And this converting has been implemented by using new algorithm characterized by finding the shortest path between two nodes in the roads network ,whatever its size, type and complication degree, in specific lengths, costs and terms and for more accuracy, to implement this algorithm, the matrix has been processed by three basic steps: The first step is to know and determine a number of the paths in the network and it is the first data which must be input to the computer in running the program.

The second step is to specify the edges within installation, each path and its numbers.

And the third step is to compare between the lengths of the calculated paths to find the shortest path.

The results of this proposed algorithm have shown that it has very high efficiency to get very accurate results.

The algorithm has been proven to reduce the size of the input data to the computer as well as to the time and effort to find the shortest path between two nodes in the designed network.