ABSTRACT
This study deals with the problem of finding shortest paths in traversing some locations within the Sokoto metropolis. In particular, It explores the use of Dijkstras algorithm in constructing the minimum spanning tree considering the dual carriage ways in the road network of Sokoto metropolis. The results shows a remarkable reduction in the actual distances as compared with the ordinary routing. These results indicate, clearly the importance of this type of algorithms in the optimization of network flows.
PDF Abstract XML References
How to cite this article
URL: https://scialert.net/abstract/?doi=tasr.2007.348.353
INTRODUCTION
Current developments in geographic information systems (GIS) technology, ensures that network and transportation analyses within a GIS environment are become a common practice in many application areas. But central problem in network and transportation analyses is the computation of shortest paths between different locations on a network. Sometimes these computation are to be done in real time.
For the sake of illustration, let us have a look at the case of an emergency call requesting fire service to rush to the scene of a fire outbreak; say in a market place or a bank. In practice, the fastest route can only be determined in real time. In some cases the fastest route has to be determined in a few seconds in order to ensure the safety of goods and lives. Moreover, when large real road networks are involved in an application, the determination of shortest paths on a large network can be computationally very intensive.
Graphs and graph algorithms have been used extensively over the years in searching for optimal topologies (Moore, 1959). This technique has also been very useful in the field of interconnection networks (Drager and Fettweis, 2002). In the same vein, Ibrahim (2006) studied the use of Kruskals algorithm in the determination of traveling sales man routes using a particular manufacturing enterprise.
The main purpose of this study is to investigate the use of Graph algorithms in optimization problems involving routing along road network in Sokoto metropolis. This is justified especially given the changing phase of the town brought about physical developments and increase in the number of dual carriage ways coupled with the surge in the cost of fuel and corresponding increase in the cost of transportation. Thus, unlike the case of traveling salesman (Ibrahim, 2006) where the locations are fixed, the shortest path problem here assumes variations in both locations and the corresponding distances. With this development, a further application of Dijkstras algorithm has been achieved in the area of transportation network.
For the purpose of clarity, some basic notions are supplied as follows:
Shortest Path Problem
The shortest paths problem involves a weighted (possibly directed) graph described by the set of edges and vertices [e, v] with a given source vertex [s]. The goal is to find the shortest existing path between [s] and any of the other vertices in the graph Each path, therefore, will have the minimum possible sum of its component edges (u, v) and weights (w (u, v)).
Spanning Tree
Is the graph obtained after improvement of the existing graph by removing all the cyclic components in it. The resulting spanning tree is therefore, always an acyclic subgraph of the parent graph.
METHOD OF COMPUTATION
In what follows, the basic method of Dikstras algorithm is provided as outlined by Ronald (1988). This algorithm was discovered by Dijksra (1959) and independently, by whiting and Hillier(1960). It finds not only a shortest (u0, v0)-path, but also all the shortest paths from u0to all other vertices of G. The basic procedure is as follows:
Let that S is a proper subset of the vertex set V such that u0 ∈ S and let denote V\S. If is a shortest path from u0 to then clearly ū∈S and the u0ū-section of P must be a shortest u0ū-path. Thereforeand the from u0 to is given by the formula
(1) |
The formula (1) is the basis of Dijkstras algorithm. It begins from the set S0 = {u0} to construct an increasing sequence S0, S1, ...Sv-1 of subsets of V in such a way that at the end of step i, shortest paths from u0 to all vertices in Si are known.
The first step is to determine a vertex nearest to u0. This is achieved by computing . Select a vertex so that using (1) we obtain thus:
(2) |
That is, is easily computed. We now set iteratively that S1 = {u0, u1} and let P1 denote the path u0, u1; this is clearly a shortest (u0, ū1)-path. In general, if the set Sk = {u0, u1,...,uk} and the corresponding shortest paths P1, P2,..., Pk were determined, we compute . Also, by (1), d(u0,uk+1) = d(u0,uj)+w(ujuk+1) for some j≤k. We get a shortest (u0,uk+1)-path by adjoining the edge ujuk+1 to the path Pj.
Illustrative Example
Consider the network in Fig. 1.
To compute the shortest path we proceed as follows:
Set u0 | = | υ0, t(u0) = 0 others are ∞ |
t(υ1) | = | min {∞, 1} = 1 |
t(υ2) | = | min {2, t(υ1)+α[u, υ2]} = min [2,3] = 2 |
t(υ3) | = | min {t(υ2)+1, 4} = min [2+1, 4] = min [3, 4] = 3 |
t(υ4) | = | min {∞, 4} = 4 |
t(υs) | = | min {t(υ4)+3, 6} = min [4+3, 6] = min [7, 6] = 6 |
t(υ6) | = | min {t(υ4)+2, 9} = min [4+2, 9] = min [6, 9] = 6 |
t(υ7) | = | min {t(υ5)+4, 9} = min [6+4, 9] = min [10, 9] = 9 |
We have obtained the following result.
Fig. 1: | A connected network |
t(υ1) | = | 1 |
t(υ2) | = | 2 |
t(υ3) | = | 3 |
t(υ4) | = | 4 |
t(υ5) | = | 5 |
t(υ6) | = | 6 |
t(υ7) | = | 7 |
These are the minimal weights from υ0 to each υi.
APPLICATION
We now consider the way and manner these concepts can be used to establish shortest routes in traversing various locations in the Sokoto metropolis using the dual carriage ways. The Fig. 2 is obtained from map of Sokoto metropolis where the arcs represent the dual carriage ways while the nodes represent the roundabouts.
Using roundabout V1; connecting Manuri road and Sultan palace as the starting point along the dual carriage ways depicted by the weighted arcs of Fig. 3. The routing layout up to the node V10; connecting Gusau road.
Computation of Shortest Paths Using Fig. 3 with the Nodes Represented by Roundabouts in the Dual Carriage Ways
• | Set uo = vo, t(uo) = o, other are ∞. |
• | t(v1) = min {∞, 2000} = 2000 |
• | t(v2) = min {∞, 1500} = 1500 |
• | Other are ∞. Thus, u1 = v1 |
• | t(v2) = min {1500, t(u1) + α(u1, v2)} = min [1500, 3000] = 1,500 |
• | t(v3) = min {t(v2) + 2000, 5500} = min [1500 + 2000,5500] = min[3500, 5500] = 3500. |
• | t(v4) = min{t(v3)+1500, 6000} = min [3500+1500,7000] = min[5000, 7000] = 5000. |
• | t(v5) = min {t(v4) + 1000, 5000} = min[5000 + 1000,5000] = min[6000, 5000] = 5000. |
• | t(v6) = min {t(v5) + 500, 4500} = min [5000 + 500,4500] = min[5500, 4500] = 4500. |
• | t(v7) = min {t(v6) + 1000, 3500} = min [4500 + 1000,3500] = min[5500, 3500] = 3500. |
• | t(v8) = min {t(v7) + 1000, 3500} = min [3500 + 1000,3500] = min[4500, 3500] = 3500. |
• | t(v9) = min {t(v8) + 2000, 5500} = min [3500 + 2000,5500] = min[5500, 5500] = 5500. |
• | t(v10) = min [t(v9) + 500, 6500] = min[5500 + 500, 6500] = min[6000, 6500] = 6000. |
Fig. 2: | Road network connectivity of Sokoto metropolis |
The algorithm stops and we obtained,
t(v1) | = | 2000m t(v6) = 4500m |
t(v2) | = | 1500m t(v7) = 3500m |
t(v3) | = | 3500m t(v8) = 3500m |
t(v4) | = | 5000mt(v9) = 5500m |
t(v5) | = | 5000mt(v10) = 6000m |
These are the minimal weights from uo to each vi. That is, the total distance from Sokoto water works to Federal Government College Sokoto reduces to only 6000 m after applying Dijktras algorithm in the corresponding routing using dual carriage ways of the Sokoto metropolis.
Similarly, if we change the starting point to begin from Sultan Abubakar college Sokoto as V1 and up to Sokoto Water Works have the following:
Computation of Shortest Paths by Making Appropriate Adjustments in Fig. 3 so that V1 is Sultan Abubakar College while V10 is the Sokoto Water Works
• | Set uo = vo, t(uo) = o, other are ∞. |
• | t(v1) = min {∞, 1000} = 1000 |
Fig. 3: | Road network connectivity of Sokoto metropolis |
• | t(v2) = min {∞, 1500} = 1500 |
• | Other are ∞. Thus, u1 = v1 |
• | t(v2) = min {1500, t(u1) + α(u1, v2)} = min [1500, 2500] = 1,500 |
• | t(v3) = min {t(v2) + 1000, 500} = min [1500 + 1000,500] = min[2500, 500] = 500. |
• | t(v4) = min{t(v3)+1000, 1500} = min [500+1000,1500] = min[1500, 1500] = 1500. |
• | t(v5) = min {t(v4) + 1000, 2500} = min [1500 + 1000,2500] = min[2500, 2500] = 2500. |
• | t(v6) = min {t(v5) + 2000, 2000} = min [2500 + 2000,2000] = min[4500, 2000] = 2000. |
• | t(v7) = min {t(v6) + 500, 2500} = min [2000 + 500,2500] = min[2500, 2500] = 2500. |
• | t(v8) = min {t(v7) + 4500, 3000} = min [2500 + 4500,3000] = min[7000, 3000] = 3000. |
• | t(v9) = min {t(v8) + 1000, 4000} = min [3000 + 1000,4000] = min [4000, 4000] = 4000. |
• | t(v10) = min [t(v9) + 1500, 5000] = min [4000 + 1500, 5000] = min [5500, 5000] = 5000. |
The algorithm stops and we obtained,
t(v1) | = | 1000mt(v6) = 2000m |
t(v2) | = | 1500mt(v7) = 2500m |
t(v3) | = | 500mt(v8) = 3000m |
t(v4) | = | 1500mt(v9) = 4000m |
t(v5) | = | 2500mt(v10) = 5000m |
These are The minimal weights from uo to each vi
CONCLUSION
It is can be established from the a fore mentioned that Dijstras Algorithm is a useful graph theoretic mechanism for optimisaton processes of network connectivity. Present results have exposed the versatility of this theoretic tool in carrying out minimization process involving construction and for itinerancy in conveyance of goods and services in different locations of a town based on the existing road network.
REFERENCES
- Dijkstra, E.W., 1959. A note on two problems in connexion with graphs. Numerische Mathematik, 1: 269-271.
CrossRefDirect Link