In today's era of highly developed information systems, one of the key tasks is to seek out the shortest path in the network – from the beginning point to the endpoint. In his book: “Shortest Path Algorithms”, F.B. Zahn argues that testing and implementing algorithms to find the shortest paths in a network is one of the most important items to address and deal with potential issues.
Development, testing and effective implementation of algorithms for locating the shortest paths in the network are important concepts in computing, as well as in geography, management, transport and other scientific disciplines and fields of work. When it comes to selecting an algorithm that tries to unravel the matter of the shortest path within the network, the appropriate algorithm will be selected counting on the given parameters of the network and the algorithm’s execution time.
Here are some examples of using several of the foremost well-known algorithms for locating the shortest paths: Dijkstra's Algorithm, Bellman-Ford Algorithm, Floyd-Warshall Algorithm, and Johnson's Algorithm.
Dijkstra's algorithm
Dijkstra’s algorithm finds the shortest path tree from a single-source node by building a group of nodes that have the closest distance from the source or the origin. Because of that, it is used in finding the shortest possible distance and directions between two geographical locations – such as in Google Maps, Waze, Maps.me, GPS Navigation, etc.
Another example would be that the firefighter department wants to develop a system that finds the shortest route between the closest firefighter department and the location of the fire, to avoid any potential delays. The same scheme works on ambulance systems for finding the closest path to the hospitals in cases of emergency. Or when logistics companies and delivery services want to develop a system that finds the shortest route between the warehouse and destinations for their delivery.
It is also used when routing data in networking and telecommunication domains to minimize the delay occurring in transmissions. If we imagine a city as a graph, the vertices represent the switching stations, and the edges represent the transmission lines. Social networking applications can also be considered using the shortest path between users by measuring the number of connections between two users. Many social networking applications are based on six degrees of separation (as in the average number of a person’s friends is six), and it can be mentioned as the distance measured in the number of connections between any two users of the network field. Even if the average number of friends for users is not big, the problem of finding the shortest paths between users is very compound from the view of this algorithm complexity. Moreover, this algorithm can be used even in-flight agenda – in a database with all airports, flights, routes, arrival time, departure time, passenger information and more.
Wherever you encounter the necessity for shortest path solutions: be it in robotics, engineering, transportation, embedded systems, factory or production plants to detect faults, errors or more – essentially, you can use this algorithm for any situation that requires discovery of the shortest path to solve the problem.
Bellman-Ford algorithm
It computes single-source shortest paths in a weighted digraph (where some of the edge weights may be negative). Dijkstra's algorithm accomplishes an equivalent problem with a lower running time but requires edge weights to be non-negative. This suggests that Bellman-Ford’s algorithm is typically used only when there are negative edge weights on the nodes.
This algorithm finds the shortest path between a given source vertex and all other vertices in the graph, a bit like Dijkstra’s – except it can be used on both weighted and unweighted graphs and it’s much easier to implement into a selected field for research.
On the Web, there are many protocols that use this algorithm. The best example is the basic network routing information protocol. This is one of the oldest Internet protocols, from its early beginning, and it prevents loops by limiting the number of hops a packet can make on its way to the destination. A second example is the interior gateway routing protocol. This protected protocol is used to help machines exchange routing data within a system.
The Floyd-Warshall algorithm
It is also an algorithm for finding the shortest paths in a weighted graph, with positive or negative edge weights but with no negative cycles. A single execution of the algorithm will find the distances of shortest paths between all pairs of vertices. Although this algorithm does not return details of the paths themselves, it is possible to reconstruct the paths with simple changes within the algorithm.
It is usually used to find all pairs of shortest path problems from a given weighted graph. As a result of this algorithm, it will generate a matrix, which will represent the minimum distance from any node to all other nodes in the graph.
The biggest difference between Floyd’s algorithm and Dijkstra’s is that Floyd's algorithm finds the shortest path between all vertices. And Dijkstra's algorithm finds the shortest path between a single vertex and all other vertices.
Floyd-Warshall algorithm is used for:
- shortest paths in directed graphs;
- transitive closure of directed graphs;
- inversion of real matrices;
- optimal routing.
When it comes to optimal routing, one is interested in finding the path with the maximum flow between two vertices. This means that, rather than taking minima, one instead takes maxima. The edge weights represent fixed constraints on flow. Path weights represent bottlenecks, so the addition operation above is replaced by the minimum operation.
It can also be used in testing whether an undirected graph is bipartite, fast computation of Pathfinder networks and maximum bandwidth paths in flow networks.
Johnson's algorithm
It is more of a way to find the shortest paths between all pairs of vertices in an edge-weighted, directed graph. It allows some of the edge weights to be negative numbers, but no negative-weight cycles may exist.
It works by using the Bellman-Ford algorithm to compute a transformation of the input graph that removes all negative weights, allowing Dijkstra's algorithm to be used on the transformed graph. This algorithm is used in job sequences and scheduling.
The Chinese Postman Theory is a famous route inspection problem that involves graph theory, a branch of mathematics and computer science. The issue of this theory is to find the shortest closed path or circuit that visits every edge of an undirected graph. When the graph has an Eulerian circuit, that circuit is an optimal solution. Otherwise, the optimization problem is to find the smallest number of graph edges to duplicate so that the resulting multigraph does have an Eulerian circuit. It can be solved in polynomials by an algorithm based on the concept of a T-join. The postman's job is to deliver all of the town's mail using the shortest route possible. In order to do so, he (or she) must pass each street once, not return, and then come back to the origin point.
Top comments (0)