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 Kruskal’s 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 Dijkstra’s 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 Dikstra’s 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
The formula (1) is the basis of Dijkstra’s 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:
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 |
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 Dijstra’s 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.