If you are a developer, whether self-taught or a college grad, chances are high that you will come across this problem to test your skills and having a keen understanding of some popular algorithms will save you a bunch.

Today, we shall see some of the most popular algorithms and this is going to be a theory and a quick introduction to how you can go around to solve such a problem depending on the different conditions put in place.

🌟 Shortest Path Problem

In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.

Shortest path algorithms are a family of algorithms designed to solve the shortest path problem.

Let's now see the different Algorithms out there. Also, let's assume an adjacency list representation, V is the number of vertices, E is the number of edges.

🌟 Bellman-Ford algorithm:

The bellman-Ford algorithm helps us find the shortest path from a vertex to all other vertices of a weighted graph.

The shortest path from Source to all other nodes in weighted directed graph even with negative edge weight (not cycle). It is slower but more versatile than Dijkstra. Complexity: O(|V|.|E|)

🌟 BFS:

Breadth-First Search is an algorithm for searching a tree data structure for a node that satisfies a given property. It starts at the tree root and explores all nodes at the present depth before moving on to the nodes at the next depth level.

Find a path from one given vertex to other nodes in the un-weighted un-directed graph.

Complexity: O(|V|+|E|). it is faster when you know vertices ahead and use appropriate data structure i.e FIFO Que for figuring out which vertex is already processed then complexity can be reduced to O(|V|)

🌟 DFS:

Depth First Search is a recursive algorithm for searching all the vertices of a graph or tree data structure.

It finds the shortest path from source to other nodes in Tree and also in Graphs. The graph may contain a cycle which means a node could be visited again and again. so we can use a boolean array to keep track of visited nodes. Otherwise, the algorithm won't stop.

Moreover, it looks deeper and deeper and goes as far as the end of the branch in the tree.
Complexity: O(|V|+|E|). and Complexity: O(|V|) space to store vertices.

🌟 Floyd-Warshall Algorithm:

It is an algorithm for finding the shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles).

It finds all pair's shortest paths in a directed weighted graph but it doesn't return details of the paths themselves.

It can be used to detect the negative weight cycle in the graph. When it finds one it terminates. it compares all possible paths through a graph between each pair of vertices. so it uses the dynamic approach, not the greedy approach.

Complexity: O(|V^3|)

🌟 Johnson's Algorithm:

Johnson's algorithm is a way to find the shortest paths between all pairs of vertices in an edge-weighted directed graph.

find all pair's shortest paths in a directed weighted sparse graph when edge weight is a positive, negative but not negative cycle.

It first uses the bellman-ford algorithm to compute the transformed graph from the original graph. It removes negative weight edges, and then Dijkstra is applied to find paths. Complexity: O(V^2 Log V + VE)

🌟 Dijkstra Algorithm:

The original version of this algorithm does not use Priority Que so Complexity is O(|V^2|) but a newer version uses this data structure so complexity becomes O(E+ V log V). and it is a faster single source shortest path algorithm.

It works by assigning a tentative weight to a visited node and infinity to un-visited nodes for visited nodes look for it's all not visited edges and select with minimum weight. and add it to the path set.

🌟 Kruskal's Algorithm:

Kruskal's Algorithm is used to find the minimum spanning tree for a connected weighted graph. The main target of the algorithm is to find the subset of edges by using which we can traverse every vertex of the graph.

It is a greedy algorithm and it can also find Minimum Spanning Forest.
Complexity: O(E log V)

🌟 Prim's Algorithm:

In computer science, Prim's algorithm (also known as Jarník's algorithm) is a greedy algorithm that finds a minimum spanning tree for a weighted undirected graph.

This means it finds a subset of the edges that forms a tree that includes every vertex, where the total weight of all the edges in the tree is minimized.

🌟 Brouvka's Algorithm:

The problem with this algorithm is that weights should be unique in the graph. Tt finds MST by examining each vertex and then putting it with a smaller weight.

This algorithm is parallel in nature but not faster than Prim's Algorithm.

Same Complexity as Kruskal's Algorithm.

🌟 A* Algorithm

A * algorithm is a searching algorithm that searches for the shortest path between the initial and the final state. It is used in various applications, such as maps.

A Search algorithm is one of the best and most popular techniques used in path-finding and graph traversals. The A search algorithm builds on the principles of Dijkstra's shortest path algorithm.

Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified source to a specified goal, and not the shortest-path tree

🌟 Seidel's algorithm

The core of the algorithm is a procedure that computes the length of the shortest paths between any pair of vertices.

Even though the algorithm is designed for connected graphs, it can be applied individually to each connected component of a graph with the same running time overall.

🌟 Summary

If there is an algorithm for a common problem, why hard-code the solution. Some of these algorithms are optimised and their time & space complexity may vary depending also on the data structures used.

The Travelling Salesman Problem (TSP) is the challenge of finding the shortest yet most efficient route for a person to take given a list of specific destinations.
It is a well-known algorithmic problem in the fields of computer science and operations research.

You could also try algorithms that can be used to solve this like Gabow's algorithm, Viterbi, Fredman & Tarjan, Pettie & Ramachandran, Hagerup 2000 etc..

Read More

🌟 Conclusion

Once again, hope you learned something today from my little closet.

Please consider subscribing or following me for related content, especially about Tech, Python & General Programming.

You can show extra love by buying me a coffee to support this free content and I am also open to partnerships, technical writing roles, collaborations and Python-related training or roles.

📢 You can also follow me on Twitter : ♥ ♥ Waiting for you! 🙂