DESIGN AND IMPLEMENTATION OF SHORTEST PATH ALGORITHM FOR NETWORK OF ROADS

Abstract

In this paper, a new method of programmed computerizing has been suggested which depends on converting the roads network to the matrix and the representation of this matrix in the adjacency matrix, that a number of rows are an equal number of columns, where the degree of this matrix is equal for a number of the edges plus one in (i) multiplied by a number of the edges plus one in (j) of the roads network (graph). The elements of This matrix will be either (1) which means an existing edge of orientation in one direction connecting between two nodes continuous connection, or (0) and which means there is no edge of orientation connecting between two nodes. And this conversation has been implemented by using a 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 the number of the paths in the network and it is the first data which must be input to the computer is running the program. The second step is to specify the edges within the installation, each path and its numbers. And the third step is to compare the lengths of the calculated paths to find the shortest path. The results of this proposed algorithm have shown that it has...