CP5602 Advanced Algorithm Analysis For the Extensions

Write the Discussion of the polynomial-time primality algorithms, and some historical survey of prior results.

Answer:

The aim of this research, is to proof that the Dijkstra’s Algorithm is instrumental in identifying the best route to transfer data by looking at the distance value by use of the status label to discover the shortest distance which may be equal to the node s(permanent) or not(temporary). Problems with establishing the shortest distance between three nodes or more nodes say a large network with so many devices communicating together can be solved using Dijkstra’s Algorithm (Choubey & Gupta, 2013). It usually begins by first assigning some initial numbers or values to all nodes then proceeds to adjusting them as more estimates that are closer to the true distance among the nodes. The Dijkstra’s Algorithm may be compared and tested to the limit; comparison may be obtained to ascertain the best out of it. By the end of this document the question of how suitable it is should be answered with appropriate explanation and the problem domain should have an amicable solution (Zheng & Zhang, 2013). In addition, a detailed analysis of the devices that employ the Algorithm. The main disadvantage of the Algorithm is time wasting when collecting the best route.

Literature Review

The aim of this chapter is to establish crucial evidence of the use of this Algorithm in technology.

APPLICATION OF DIJKSTRA’S ALGORITHM 

It is used in robotics manipulation, due to its ability to control robots without the need of a professional operating it (Xu & Wang, 2012). An example is where a robot has to navigate safely around an object without knocking walls, rocks or even people. This is especially applicable when developing video games, moving space equipment in planets like Mar, when using mapping devices used to give the best and shortest path to a destination and finding out the shortest route that a computer can use to send emails or telephony using the existing infrastructure (Chatterjee, 2010).

USE OF DIJKSTRA’S ALGORITHM IN COMPUTER GAMES

It is used to identify the path that can be taken by an object navigating through say a virtual building, where one can adequately plan where to pass and where to avoid. The virtual building is basically an abstract of the real building (Bardi & Lopez, 2015). Apart from a building it can also guide through an open space where one may want to drive through the best road in a racing game to take advantage of other racers.

APLPLICATION OF DIJKSTRA’S ALGORITHM IN ROBOTICS 

Robots navigating in open or closed environment should be schedulde and navigation properties set in order to for them to navigate safely (Talea, 2017 ). Mostly, pathfinding units are preinstalled in order for them to move easily and safely without the need of human intervention. Combined with other algorithms, such as the A* Algorithm the Dijkstra’s Algorithm can be made even better as complex and dangerous activities such as military functions and medical experiments and research can be carried out (Jahan & Hasan, 2011).

APPLICATION IN SELF-DRIVING CARS

It is the use of cars with sensors that can detect objects, find routes and be programmed to make choices based on the environmental factors. It has the ability of altering its path based on the information collected from the sensors mounted on it (Zhao, 2018). The USA defense organ DARPA has previously tried motivating companies to develop self-driving cars for its advanced military programs. Other companies such as Uber; have tried innovating self-driving cars for their taxi programs to reduce their cost of operations.

THE NAVIGATION SYSTEM FOR THE BLIND

A combination of the Dijkstra’s Algorithm with other similar algorithms can be used to navigate blind people around difficult angles such as around trees, corners (Nandini, 2015). This can be attained by arching a moderate speed and carefully calculated steps, this employs simple calculations and ultrasound to safely find targets. By carefully improving response time offered by the Dijkstra’s algorithm, these devices will be more efficient and effective apart from just reducing the size (Maimone & Leger, n.d.). However, these advances have had their fair share of critics as they lack support desired when operating in an indoor environment.

APPLICATION OF DIJKSTRA’S ALGORITHM IN TRANSPORTATION

It’s the most significant use of the algorithm as it is used to safely move people around as well as goods from one place to another using the safest path possible. In the current world having in mind the traffic problems and commitments such as work being very demanding. People will always want the best and quickest solution (Xiao-Yan & Yan-Li, 2010). Hence, they may want to know where they are, how far they are and where they are heading. The use of tools such as google maps and Microsoft maps offers this service to its users. In comparison to other Algorithm used to solve the same problem domain Dijkstra’s Algorithm offers more possibilities from search than any other Algorithm as shown by an experiment done by Jacob El Ato, who did an Experiment using a large database which tested almost all Algorithm similar to it and proved that the Algorithm offers the most empirical search result.

The dynamic behavior of applications used in routing, forces the need to supple and form effective techniques for routing, with a tight eye kept at the processing time and utilization of available memory. Regrettably, research does hardly gives the best algorithm to select when faced by a dilemma (Alija, 2015). However, some recent papers unlike those that have had a lot of research put into them hardly suggest the best algorithm, but they are trying to give the best from their school of thought which is at times confusing.The following paper tries to give the above insight into the gap. 

While travelling, the most important details is about where one is heading and what distance and time it will take. If one is not familiar to a place, a lot of time may be wasted trying to gate the location of the current location (Tompkins & Stentz, n.d.). Some companies have made significant development into this area, some software such as google maps which is the most widely used navigator. This software has enabled entry of just two major entries to get the path to a given area, by just giving the starting point and the ending point one can determine the distance to take.

According to (Mustafa, 2007), there are so many other possible algorithms that can make similar application. The most common way is to walk openly headed until an obstacle prevents continuing with the process (Kilincarlsan, 2007). If an object is met, the algorithm automatically changes the direction, in-case of a cars navigation system the system alerts the driver by asking for change in direction. If no change it recalculates based on previous output and gives an alternative approach or asks for new entry.

COMPARISON OF THE DIJKSTRA’S ALGORITHM TO SIMILAR ALGORITHMS

DIJKSTRA’S ALGORITHM VERSUS SHORTEST PATH ALGORITHM

The biggest difference is, the shortest path Algorithm suffers from identifying the path that has the least travel time from a group of possible routes within the same network to its intended network (Arisoylu, 2016). It however, has an advantage over Dijkstra’s Algorithm in that its ease of obtaining an optimal route from one location to another (Alpdundar, 2016).

NB: the shortest time can be explained as two possible variables, short or fast.

DIJKSTRA’S ALGORITHM VERSUS DEPTH SEARCH ALGORITHM

Its main difference from Dijkstra’s Algorithm, is that it explores each rout before picking the best. It is terminated at either the goal or the las node and then starts over again till the end product is reached. It starts by the node nearer to the goal rather than starting from the beginning like Dijkstra’s (Tompkins & Wettergreen, n.d.). Th following is a close look of the depth search algorithm against the Dijkstra’s.

DIJKSTRA’S VERSUS A*ALGORITHM

A*Algorithm has a higher preference compared to other algorithms. Having been developed in1968, it offers universal search options. Its most used in real-time systems such as game livestreaming or online gaming, its main difference when compare to Dijkstra’s algorithm is flexibility (Ramzi & Mahmoud, 2013). Instead of assigning values and then adjusting these values among the many nodes, it uses a starting and end points to determine routing.

	O				X

 The algorithm then proceeds to look in the surrounding till when it will discover the end point.

To keep track of the nodes an open list is initiated to store them. Once it re-inspects them and verifies then it then proceeds to store them in closed list (Möhring & Schilling, 2016). If a node does not show signs of being walkable it’s not even considered by the Algorithm for the open list.

!	!	!
!	O	!			X
!	!	!

P	P	P
P	O	P			X
P	P	P
	O				X

This is how it checks to see the end point.

Both the Dijkstra’s and the A*algorithm use the parent node to know the shortest path.

DIJKSTRA’S ALGORITHM VERSUS THE MANHATTAN DISTANCE

The Manhattan distance is got from addition of the differences between the X and Y variables. Its main disadvantage over Dijkstra’s is that it suffers from overestimation. Its not applicable where the expectations, is getting the optimal path to a given node.

	O
					X

This grid is used to solve the Manhattan distance problem domain.

THE DIJKSTRAS ALGORITHM

NOTATIONS USED IN DIJKSTRA’S ALGORITHM

Before exploring the area surrounding the working of pseudo-code it is imperative to recognize how the algorithm functions. The algorithm functions through resolving the sub-problem k, that computes the shortest route from source to any vertices among the k closest vertices to the source (Yan, n.d.). For this algorithm to perform to its expectations, it should have a direct-weighted graph and all its edges should be non-negative. If it happens to have edges which are negative then the actual shortest route may not be obtained at all.

During the last phase of computing the value of k, there should exist a set known as Frontier which has k vertices that houses all the vertices that are closest to source and every other vertices that falls outside the range of the frontier will be executed on and stored in the New Frontier. The shortest route derived is preserved in sDist[w]. Which stores the approximate distance from s to w (Latuconsina & Purboyo, 2017). Dijkstra’s algorithm solves for the next least far away vertex through storing the New Frontier vertices in a priority-min queue. The algorithm functions through keeping the least value of the distance of vertex v from the source in-form of an array, sDist. The least distance of the source to itself is zero. Distance for all other vertices is initialized to infinity to indicate that those vertices are not yet processed (Otte, 2015). After the algorithm finishes the processing of the vertices will have the least distance of vertex w to s. two groups/sets are stored in the Frontier and New Frontier which helps in the processing of the algorithm. Frontier keeps k vertices that are in close proximity to the source, will have already computed least distances to these vertices, for routes constrained upto k vertices. The vertices that resides exterior of Frontier is stored inside a set known as New Frontier.

Dl represents a node l

t or p represent a permanent or temporary path between nodes, it is normally used in status labeling.

i or j is the overall cost of routing through a link.

STEPS USED IN ALGORITHM.

1. Initializing

First of all the node s, also the start node should be assigned zero, its state becomes (0,p),

Precede all nodes values each a different number where none of them is limited. The current node which is default node s, should be assigned(0,p) and all other nodes should follow with a value to infinity (Michel, 2016). All having (∞,t).

2. Update of distance and value of node

Find all nodes that can be accessed from the current default node and the update their initial values. The current node is assigned i and the linkage between nodes is (I,j), the distance is updated in the following manner, J is the set holding the values i and j.

Updated dj =(dj,di + cij) MIN , where the Cij represents network cost (Gonçalves, 2010). To know the smallest distance between nodes, the following is done to obtain dj within the set J.

Find j min

j is within range of J

dj = dj

Then alter the node that is labeled j as permanent and declare it as present node.

3. The final step is trying to access the all temporary nodes the entire process should be terminated as the process is already complete and there is nothing to add to it.

If not retry step two to see there is something you omitted.

A SETUP TO OBTAIN THE SHORTEST ROUTE

We shall explain the working of the Dijkstra’s algorithm from node 1.

Step 1, Initialize

Node 1 is the current

Node

• Node 1 state is (0, p)
• All additional nodes have the state (1, t)

Nodes 2, 3,and 5 are accessed from node 1

• the distance have been updated as follows

d3 = min{1, 0+4} = 4

d4 = min{1, 0+8} = 8

d6 = min{1, 0+10} = 10

• From the above data, when carefully analyzed we can confirm that it is node d3 has the smallest distance from node 1.
• The node 2 status now changes to permanent from temporary, so new state becomes (7, p),

The other two statuses all become temporary.

• Node 2 now changes identity and becomes the new current state.

This process should be made recursive and should be repeated till all nodes are made permanent, go back to two if not completed on first retry.

Since all nodes around node 1 have been taccounted for, it should be ignored and assumed; hence, it should not be repeated.

The least route to node 1 should be taken; node 3 should now be identified as present node. Its neighbors will receive an update with new distances.

There is also another way to go around step 2,

Node 4 and 5 can be accessed, from node two which is the current node

• All distances should be updated as follows

nodes

d4 = min{8, 5+ 6} = 9

d5 = min{2, 6+11} = 11

• We now make a discovery that the distance from node 4 to node is less as compared to node 5, hence, we have to change the current state to node 4.
• Node 4 therefore becomes permanent, but node 5 does not change and is still the only temporary node available and so we have to go back and redo the entire process again.
• Node 4 assuming the current node means that node 3 three is no longer the current state node because it was the previous node and now we have a new permanent node which has to assume the properties of the predecessors (Aguilera-Venegas, et al., 2015).

Redo step two again, since the last node has not been made permanent to terminate the operation.

Node 5 and 6 can be accessed by the current state 4

• The new updated distance is as follows

D5 = min{8, 8+9} = 20

D6 = min{10, 9+3} = 12

• Node 5 now has the highest distance from node 4 but since node 6 now has the least distance we change form current state 4 to new current state 6.
• Now node 6 becomes the new current node and hence, assumes a permanent role. Hence the only non- permanent node is node 5.
• Current node becomes node 6

Perform the operation once again.

Node 5 is now accessed by the new current state 6.

• Initialize to new values for the distance as shown below.

d5 = mn{1, 9+10} = 19

• Since there is no other node, node 6 automatically assumes current state.
•  the new current state as previously stated becomes node 5.

Now notice what happens as there is no other node that node 5 can access the operation can not proceed and therefore has to terminate at that.

AN EXAMPLE OF A CODE TO EXECUTE A DIJKSTRA’S ALGORITHM

Dijkstra’s(v1, v2):

for every vertex vx: // Initializing

vx's displace := infinity.

vx's prev := none.

vx's displace := 0.

List := {vertices}.

while theListIsNotEmpty:

vx := List vertex that has least distance should be remove.

V should be marked to be known.

for every n that is an unknown neighbor of v:

disp := vx's displace + edges (v, n) weight.

if disp is lesser than distance of n:

n's displace:= disp.

n's prev := v.

reconstruct path from v2 back to v1,

The above code is used to calculate vertex from a cloud for storage

OPERATIONS ON ISSUES OF TIME QUEUE

The efficiency is expressed in Big-P symbolization. Big-P provides an alternative approach on expressing how input impacts on the run time of the algorithm. It provides a higher bound on run time (Coskun & Ok, 2013). The efficiency in Dijkstra’s algorithm, varies dependent on |V|=n’s delete-minus and |E| updates for priority queues that were used (Garg, 2018).

Fibonacci heap is applied when complex is P( | EF| + | V | log | V | ) ,

Which helps get the best answer? The delete_mins operation picks P(log|V|).

When standard binary heap gets applied the complexity is P( | F |log |F|),| F |

Log |F] originates from |F| an update on standard heap .

A set applied in complexity gives the following P(|F|+|V|2). P(V|2)

It comes from |V| used to scan and get the shortest distance between nodes..

The following code implements the list method.

• |V| vertex and |F| edges
• Initialize P(|V|)
• While loop P(|V|)
  • Find and remove min distance vertices P(|V|)
• Potential |P| update
  • Update cost P(1)

Total time P (|V²| + |F|) = P (|V²|)

The code operates in the following way.

A sparse graph, (graphs that have less compared to |V²| edges) Dijkstra's using a priority queue

• Initialize P(|V|) using P(|V|) build heap
• While loop P(|V|)
  • remove after discovering min distance vertices P(log |V|) by P(log |V|) delete min
• Potential |F| update
  • Updates on costs P(log |V|) use decrease key

total_time P(|V|log|V| + |F|log|V|) = P(|F|log|V|)

|V| = P(|E|) assume that it is graph connected.

IMPORTANCE OF DIJKSTRA’S ALGORITHM

A lot of problems can be uniquely solve using algorithms by identifying shortest route or path problems, Hence, this makes Dijkstra’s algorithm more powerful also gives a reliable tool (Aviram & Shavitt, 2015).

Example:

• Dijkstra’s algorithm is relevant when finding the route between two locations, an example is using google to give directions, i.e. use of Google maps.
• In a internetworking and communication applications, Dijkstra’s algorithm helps in solving and handling min-delay route problem (which happens to be shortest path problem). In networking routing helps get the best route for a data packet with very little delay (Ozdenizci & Aydin, 2011).
• Used to solve a wide range of shortest path problems in many fields such as industries where robotics are used.

. It is used in traffic lights to track origin or destination of vehicles.

DISADVANTAGES OF DJKSTRA’S ALGORITHM

1. The major disadvantage is that it performs blind search, therefore it exhibits a time wasting as it does such sequentially (Dramski, 2012). That is step by step till it completes it.
2. It also suffers from inability to handle negativity. This means it would end up giving an inconsistent shortest path, it will mostly likely be untrue.

References

Aguilera-Venegas, G., L.Galán-García, J. & Á.Galán-García, M., 2015. A new Probabilistic Extension of Dijkstra’s Algorithm to simulate more realistic traffic flow in a smart city. Applied Mathematics and Computation, Volume 267, pp. 780-789.

Alija, A. S., 2015. ANALYSIS OF DIJKSTRA’S AND A* ALGORITHM TO FIND THE SHORTEST. [Online]
Available at: eprints.uthm.edu.my/7478/1/AMANI_SALEH_ALIJA.pdf
[Accessed 8 September 2018].

Alpdundar, S., 2016. Comparison of Dijkstra’s algorithm and Floyd–Warshall algorithm. [Online]
Available at: https://www.selmanalpdundar.com/comparison-of-dijkstras-algorithm-and-floyd-warshall-algorithm.html
[Accessed 5 September 2018].

Arisoylu, M., 2016. An initial analysis of packet function-aware extension to Dijkstra algorithm for wireless networks. Journal on Wireless Communications and Networking, pp. 1-15.

Aviram, N. & Shavitt, Y., 2015. Optimizing Dijkstra for real-world performance. [Online]
Available at: https://arxiv.org/pdf/1505.05033.pdf
[Accessed 6 September 2018].

Bardi, M. & Lopez, J. P. M., 2015. A Dijkstra-type algorithm for dynamic games. [Online]
Available at: https://hal.archives-ouvertes.fr/hal-00881218v2/document
[Accessed 5 September 2018].

Chatterjee, U., 2010. Applications of Three Common Graph Theoretical Algorithms. [Online]
Available at: https://raysforexcellence.squarespace.com/.../Chatterjee_Applications_of_Three_Com
[Accessed 9 September 2018].

Choubey, N. & Gupta, B. K., 2013. Optimal Route Computation For Online Public Transport Enquiry System. ITSI Transactions on Electrical and Electronics Engineering (ITSI-TEEE), 1(1), p. 2320 – 8945.

Coskun, V. & Ok, K., 2013. A Survey on Near Field Communication (NFC) Technology. Wireless Personal Communications: An International Journal, 71(3), pp. 2259-2294.

Dramski, M., 2012. A comparison between Dijkstra algorithm and simplified ant colony optimization in navigation. Maritime University of Szczecin, 29(101), p. 25–29.

Garg, D., 2018. Dynamizing Dijkstra: A solution to dynamic shortest path problem through retroactive priority queue. Journal of King Saud University - Computer and Information Sciences, pp. 1-10. https://doi.org/10.1016/j.jksuci.2018.03.003.

Gonçalves, A. B., 2010. An extension of GIS-based least-cost path modelling to the location of wide paths. International Journal of Geographical Information, 24(7), p. 983–996.

Jahan, S. & Hasan, M. S., 2011. A Comparative study on Algorithms for Shortest-Route Problem and Some Extensions. International Journal of Basic & Applied Sciences, 11(6), pp. 167-177.

Kilincarlsan, M., 2007. IMPLEMENTATION OF A PATH FINDING ALGORITHM FOR THE NAVIGATION OF VISUALLY IMPAIRED PEOPLE. [Online]
[Accessed 7 September 2018].

Latuconsina, R. & Purboyo, T. W., 2017. Shortest Path Algorithms: State of the Art. International Journal of Applied Engineering Research, 12(23), pp. 13610-13617.

Maimone, M. W. & Leger, P. C., n.d. Overview of the Mars Exploration Rovers' Autonomous Mobility and Vision Capabilities. [Online]
Available at: https://www-robotics.jpl.nasa.gov/publications/Mark.../mer_autonomy_icra_2007.pdf
[Accessed 8 September 2018].

Michel, F., 2016. Dijkstra's Shortest Path Algorithm: Step by Step. [Online]
Available at: https://www.maplesoft.com/applications/view.aspx?sid=153973
[Accessed 7 September 2018].

Möhring, R. H. & Schilling, H., 2016. Partitioning graphs to speedup Dijkstra's algorithm. Journal on Wireless Communications and Networking, 11(8), pp. 1-29.

Nandini, D., 2015. A novel path planning algorithm for visually impaired people. Journal of King Saud University - Computer and Information Sciences.

Otte, M., 2015. Modifying Dijkstra's Algorithm to Solve Many. [Online]
Available at: https://www.semanticscholar.org/paper/Modifying-Dijkstra-%27-s-Algorithm-to-Solve-Many-of-Otte/c2f980bcbc13bd8d145b6b3a0fff3718545b12cc
[Accessed 9 September 2018].

Ozdenizci, B. & Aydin, M. N., 2011. Development of an Indoor Navigation System Using NFC Technology. [Online]
Available at: https://www.researchgate.net/publication/224247706_Development_of_an_Indoor_Navigation_System_Using_NFC_Technology
[Accessed 8 September 2018].

Ramzi, B. & Mahmoud, T., 2013. Dijkstra Algorithm Implementation on FPGA Card For Telecom Calculations. International Journal of Engineering Sciences & Emerging Technologies, 4(2), pp. 110-116.

Talea, M., 2017 . Application of Dijkstra algorithm for solving interval valued neutrosophic shortest path problem. [Online]
Available at: https://ieeexplore.ieee.org/document/7850151/
[Accessed 5 September 2018].

Tompkins, P. & Stentz, A., n.d. Global Path Planning for Mars Rover Exploration. [Online]
Available at: https://www.ri.cmu.edu/pub_files/pub4/tompkins...3/tompkins_paul_2004_3.pdf
[Accessed 08 September 2018].

Tompkins, P. & Wettergreen, D., n.d. Global Path Planning on Board the Mars Exploration Rovers. [Online]
Available at: https://www.ri.cmu.edu/publications/global-path-planning-for-mars-rover-exploration/
[Accessed 8 September 2018].

Xiao-Yan, L. & Yan-Li, C., 2010. Application of Dijkstra Algorithm in Logistics Distribution Lines. [Online]
Available at: citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.403.7842&rep=rep1.
[Accessed 7 September 2018].

Xu, Y. & Wang, Z., 2012. The Application of Dijkstra's Algorithm in the Intelligent Fire Evacuation System. [Online]
Available at: https://ieeexplore.ieee.org/document/6305611/?denied
[Accessed 7 September 2018].

Yan, M., n.d. The Dijkstras Algorithm. [Online]
Available at: https://math.mit.edu/~rothvoss/18.304.3PM/Presentations/1-Melissa.pdf
[Accessed 6 September 2018].

Zhao, J., 2018. The key technology toward the self-driving car. International Journal of Intelligent Unmanned Systems, 6(1), pp. 2-20.

Zheng, J. & Zhang, Z., 2013. A PostGIS-Based Pedestrian Way finding Module Using Open Street Map Data. [Online]
Available at: eprints.maynoothuniversity.ie/8086/1/AW-PostGIS-2013.pdf
[Accessed 8 September 2018].