| twork Using Dijkstra‘s-Bellman-Ford Algorithm‖. Nowadays,
traffic has become one of the major problems that people encounter
in our daily lives. The researchers computed a shortest path using
Dijkstra‘s Algorithm and Bellman-Ford Algorithm that could be
possibly provide solution to traffic congestion. The shortest path
problem is the problem of finding a path between two vertices. In the
graph, the sum of the weights of its constituent edges is minimized. In
finding the shortest path the researchers applied the Dijkstra‘s
Algorithm and the Bellman-Ford Algorithm to find the shortest path in
the road network.
The best application of the shortest path algorithm is
through a road network. The researchers analyzed the concepts and
principles of Dijkstra‘s Algorithm and Bellman-Ford Algorithm as a
shortest path routing schemes for road network. They also designed
and developed road network simulation model to implement the said
algorithms.
The developmental research involved the situations in
which the product development process was analyzed and described.
A road network model design was used to simulate the actual
applications. The output of the study focused on promoting better
understanding of Dijkstra‘s Algorithm and Bellman-Ford Algorithm as
a solution to find the shortest path in a road network.
A shortest path problem is used for finding the path with
minimum travel time and cost for one or more origins to one or more destinations through a connected network. It can be used on a variety
of applications in road transformation.. There are a great number of
algorithms that can be used to exploit the application on shortest
path problem but the study focused on the two of the most wellknown algorithm.
There are differences and similarities between the
principles of Dijkstra‘s Algorithm and Bellman-Ford Algorithm. In
terms of searching the shortest path, both algorithms can be applied
to graphs that are directed or undirected. They both offer efficient
execution of solutions. The difference lies on the capacity to handle
graphs with non negative edges weights.
A hybrid of Bellman–Ford and Dijkstra‘s algorithm is
suggested, improving the running time bound upon Bellman–Ford for
graphs with a sparse distribution of negative cost edges. The
resulting hybrid algorithm is expected to combine their best features
and hasten the process of searching for the shortest path.
The researchers arrived at a conclusion that the Dijkstra‘s
Algorithm is faster than Bellman-Ford algorithm in computing the
shortest path, Using algorithmic analysis the researchers were able to
create a simulation of a road network which caters to Dijkstra‘s and
Bellman-Ford algorithm and using algorithmic analysis the
researchers evaluated that the hybrid form of the Bellman-Ford and
Dijkstra‘s algorithm is better than its individual counterpart.
The researchers hereby recommend that since the hybrid
form of the Bellman-Ford and Dijkstra‘s algorithm is better than its
individual counterpart, future researchers, computer science students,
teachers, vehicle drivers and traffic engineers can focus on combining
other shortest path algorithms to be able to find a better hybrid
outcome. |
| Books
Drozdek, Data Structures and Algorithms in Java, 2010
Drozdek, Data Structures and Algorithms in C++, 2010
Fishwick, Simulation Model Design and Execution, 1995
Joyner, Nguyen and Cohen, Algorithmic Graph Theory, 2011
Gould, Ronald, Graph Theory, 2012
Online References
http://www.codeproject.com/Articles/19919/Shortest-Path-Problem-Dijkstra-sAlgorithm
Vol.6 - No. 1 - December 2016 |Page.:.22
http://www.cise.ufl.edu/~fishwick/introsim/node1.html
http://www.techterms.com/definition/graphics)
http://hem.passagen.se/des/hocg_1960.htm)
http://securipedia.eu/mediawiki/index.php/Road_network
http://www.websters-online-dictionary.org/definitions/Computers %20Graphics
Dijkstra algorithm (n.d.). retrieved – November 2, 2015 from
http://vasir.net/blog/game_development/dijkstras_algorithm_shortest_path/
Shortest Path Problem(n.d.). retrieved – November 2, 2015 from
http://mathworld.wolfram.com/ShortestPathProblem.html
Traffic Congestion (n.d.). retrieved – November 2, 2015 from
http://www.ukessays.com/essays/transportation/traffic-congestion.php
Shortest Paths (n.d.). retrieved – November 2, 2015 from
http://algs4.cs.princeton.edu/44sp/
Blender(n.d.). retrieved – November 11, 2015 from
http://store.steampowered.com/app/365670/
Unity(n.d.). retrieved – November 11, 2015 from
http://code.tutsplus.com/tutorials/introduction-to-unity3d--mobile-10752
Maya(n.d.). retrieved – November 11, 2015 from
http://www.edulearn.com/article/what_is_autodesk_maya.html
http://home.ubalt.edu/ntsbarsh/simulation/sim.htm#rwis
http://www.inf.utfsm.cl/~hallende/download/Simul-2-
2002/Introduction_to_Modeling_and_Simulation.pdf
Related studies
K.Rohila, P. & Gouthami, Priya M, Dijkstra‘s Shortest Path Algorithm for Road
Network, 2014
Thippeswamy, K, Hanumanthappa, J. & Manjaiah, D. H,, A Study on Contrast and
Comparison between Bellman-Ford Algorithm and Dijkstra‘s Algorithm,
2010
Olle Hassel, Shortest Path Routing in a Road Network: Finding an Easily
Implementable Algorithm Given Efficiency Constraints
Michael T. Winn, A Road Network Shortest Path Analysis: Applying Time-Varying
Travel-Time Costs For Emergency Response Vehicle Routing, 2014
Gustaf Jansson, Traffic Control with Standard Genetic Algorithm a simulated
optimization control of a Traffic Intersection, 2010
Tamás Tettamanti, Advanced Methods for Measurement and Control in Urban
Road Traffic Networks, 2010
Vaibhavi Patel & Prof.ChitraBaggar, A Survey Paper of Bellman-Ford Algorithm
and Dijkstra Algorithm for Finding Shortest Path in GIS Application, 2014 |