Application of Dijkstra Algorithm to Proposed Tramway of a Potential World Class University ()
Received 30 December 2016; accepted 21 March 2016; published 24 March 2016
1. Introduction
One of the major advantages of rail transit, particularly Trams, is that it can provide a highly efficient and very attractive mode of public transit to provide access to and from hostels and places on university campuses [1] . Rail is ideally suited to accommodate the surges of passenger volumes that are often associated with University main activity centres [2] - [4] . Most campuses in sub Saharan Africa are served by heavily fossil fuel dependent automobiles (such as busses, cars, motorcycles and tricycles). A tram system is a rail-based transit system that runs mainly or completely along streets (i.e. with street running), with relatively low capacity and frequent stops [5] [6] . A tram (also known as tramcar; and in North America known as streetcar, trolley or trolley car), is a rail vehicle which runs on tracks along public urban streets (called street running) [1] [7] . Tram network is presently in existence in Melbourne University, Australia. The Melbourne tramway network is a major form of public transport in Melbourne, the capital city of the state of Victoria, Australia [2] . As at May 2014, the network consisted of 250 kilometres of track, 493 trams, 25 routes, and 1763 tram stops. It is the largest urban tramway network in the world, ahead of the networks in St. Petersburg (205 km), Berlin (190 km), Moscow (181 km) and Vienna (172 km) [2] [6] . Members of the university community have to travel from one point to another on campus for different reasons, ranging from attending lectures to attending meetings. In order to travel and arrive at destinations in good times, movement path has to be chosen wisely. This is an example of shortest path problem and the weight will be the time cost. Certainly different routes will involve different stations and pathways [8] [9] . For this paper, we assume that the tram network will cover only the following spots on covenant university campus, which represent the stations, in Table 1. We also assume that the average speed on campus is 50 km/h, and that the time cost is always directly proportional to the distance covered. Table 2 shows the initial distance between two given spots (stations) on campus. Figure 1, on the other hand, shows the directed weighted graph showing the network of the proposed rail paths, with the edges as the initial distance between two given stations. The network, formed using Table 2, is to be optimized, by finding the shortest path from station A (Canaan land entrance gate), which is our starting node, to station U (Electrical Engineering department), which is our target node. Dijkstra algorithm is applied on the network in Figure 1 to find the shortest distance from node A
![]()
Table 1. Proposed rail stations on camp.
![]()
Figure 1. Directed graph showing the distances between the nodes.
to node. The main advantage of this work is the fact that a simple algorithm, such as Dijkstra algorithm, can be applied, with some assumptions, to estimate the shortest part of a proposed tramway in a potential world class university. Tramway transit system is very new in universities in sub-Saharan Africa countries. Tram system will soon be the transit mode of choice among many sub-Saharan Universities of lower to medium population density. Tram systems are very safe in pedestrian environments ~ far safer than automobiles―while providing convenient surface access to the public. Some of the advantages of this would be lower cost and greater flexibility, reduction in carbon dioxide emission and convenience, especially during rainy season. Also, the following are other benefits of this transportation system; extension of rail network to areas currently not served by campus shuttle cars, reduction in cost of transportation within the covenant university, reduction in carbon monoxide in the air, making the university cleaner and always quite, making the university accessible and socially vibrant [2] [6] [9] . Dijkstra’s algorithm is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks [9] [10] . The algorithm exists in many variants; Dijkstra’s original variant found the shortest path between two nodes, but a more common variant fixes a single node as the “source” node and finds shortest paths from the source to all other nodes in the graph, producing a shortest path tree [4] [10] . Dijkstra Algorithm was made popular by Edger Wybe Dijkstra, a Dutch computer scientist from Netherland. He was known for his many essays on programming. The object of this paper therefore, is to present an optimisation model [3] [9] [10] , which deals with the selection of the routes on which services will be offered using TRAM system in Covenant University [6] [11] [12] . This study exposes the need for a Tram transportation system on campus with expanded rail network to meet the growing needs of the university as regards mobility. It is also intended to know how to move from one point to another in a potential world class university, in order to save time and reduce cost [13] [14] . This is a single source shortest path problem [10] [11] . Dijkstra Algorithm is used to find solution to this problem. The following conditions are assumed in this paper: the graph in Figure 1 is directed, all edges have non-negative weights, and the graph is also connected. Figure 2 shows a Tram in motion [8] [12] . The shortest path obtained in the work, represents route to be taken in order to optimize the proposed tramway [5] [7] .
2. Formulation of Problem
The Data collected are shown in Table 1 and Table 2. The weighted directed graph is drawn using the information from the tables.
![]()
Table 2. Distance between two locations/stations (x10).
Assumptions
The following assumptions are claimed in this work:
1) There is no waiting time at the stations.
2) The shortest distance in this work means shortest time costing.
3) One-way travel condition is considered.
3. Problem Solution
3.1. How Dijkstra Algorithm Works
Dijkstra’s algorithm gives shortest distance between a source vertex and a target vertex in a weighted graph. Let the node at which we are starting be called the initial node (node A). Let the distance of node B be the distance from the initial node A to B. Dijkstra’s algorithm will assign some initial distance values and will try to improve them step by step. The procedure is as follows (Nilesh More, 2014):
1) Assign to every node a tentative distance value: set it to zero for our initial node and to infinity for all other nodes.
2) Set the initial node as current. Mark all other nodes unvisited. Create a set of all the unvisited nodes called the unvisited set.
3) For the current node, consider all of its unvisited neighbors and calculate their tentative distances. Compare the newly calculated tentative distance to the current assigned value and assign the smaller one. For example, if the current node A is marked with a distance of 5, and the edge connecting it with a neighbour B has length 4, then the distance to B (through A) will be 5 + 4 = 9. If B was previously marked with a distance greater than 9 then change it to 9. Otherwise, keep the current value.
4) When we are done considering all of the neighbors of the current node, mark the current node as visited and remove it from the unvisited set. A visited node will never be checked again.
5) If the destination node has been marked visited (when planning a route between two specific nodes) or if the smallest tentative distance among the nodes in the unvisited set is infinity (when planning a complete traversal; occurs when there is no connection between the initial node and remaining unvisited nodes), then stop. The algorithm has finished.
6) Otherwise, select the unvisited node that is marked with the smallest tentative distance, set it as the new “current node”, and go back to Step 3.
3.2. Application of the Dijkstra Algorithm to Our Problem
Let node A be the initial node. Let the distance between the nodes be as shown in Figure 1. In order to improve on these initial distances we will try to improve on them step by step, using the Dijkstra’s algorithm procedure as explained in Section 3.1. This resulted in Table 3 below.
4. Result Discussion
Table 3 shows the result of the application of Dijkstra’s algorithm to the weighted graph in Figure 1. It can be deduced from this table that the required shortest path from the initial node A to the target node U is as follows:
(1)
By interpretation, starting from Canaan land entrance gate, the rail path should go through Covenant University gate, then pass through CU main round about, then the Chapel parking lot, then CU Centre for learning and research, then through the centre for development studies, then finally through café 2 to the Electrical Engineering department.
From Table 3, it can be shown that the minimum distance from node A to node U is 805 meters as shown below:
![]()
Table 3. The matrix of distances between stations resulting from application of Dijkstra algorithm.
(2)
The actual shortest distance, therefore, is 805 meters. That is 0.805 km from Canaan land entrance gate to the Electrical Engineering department. From Table 3, we can show the shortest distance between nodes from the initial node A, from where the above shortest distance is derived, as follows:
(3)
(4)
(5)
(6)
(7)
(8)
(9)
(10)
![]()
(11)
![]()
(12)
![]()
(13)
![]()
(14)
![]()
(15)
![]()
(16)
From (3) above, the initial distance between the starting node A to C, D and B are 25 m, 200 m and 27 m respectively.
From (4): the shortest distance of I from A is 207 m and it is through B.
From (5): the shortest distance of H from A is 54 m and it is through C.
From (6): the shortest distance of E from A is 470 m and it is through D.
From (7): the shortest distance of F from A is 470 m and it is through E.
From (8): the shortest distance of L from A is 470 m and it is through F.
From (9): the shortest distance of J from A is 470 m and it is through H.
From (10): the shortest distance of O from A is 470 m and it is through J.
From (11): the shortest distance of S from A is 470 m and it is through K.
From (12): the shortest distance of Q from A is 680 m and it is through L, the shortest distance of G from A is 675 m and it is through L. the shortest distance of K from A is 1640 m and it is through L.
From (13): the shortest distance of P from A is 780 m and it is through M the shortest distance of O from A is 765 m and it is through M.
From (14): the shortest distance of T from A is 651 m and it is through O.
From (15): the shortest distance of M from A is 735 m and it is through Q the shortest distance of R from A is 750 m and it is through Q.
From (16):the shortest distance of U from A is 805 m and it is through R.
5. Conclusion
Analysis of the shortest path of a proposed tramway for a potential world class University is carried out in this paper using the Dijkstra Algorithm. Covenant University is used as a case study. Some important spots on the campus are identified as the tramway stations. The Canaan land gate is using as the starting point, which represents the initial node A on the weighted graph in Figure 2. The last station is taking to be the Electrical Department, which represents our target node U. From the results obtained, it can be concluded that the shortest distance between the Canaan land gate and the department of Electrical Engineering is 805 meters. This has to be put into consideration during construction of the tramway so as to cut cost and save time of the users of the tram, as a result of the shortest route identified in this study.