DAA - Dijkstra's algorithm(BCA-IV semKSWU)

Dijkstra's algorithm

        Dijkstra's algorithm is a algorithm used in the field of design and analysis of algorithms. It helps us find the shortest path between two nodes in a graph, which can be applied to various real-world scenarios like navigation systems, network routing, and more.

    The algorithm is named after its inventor, Edsger Dijkstra, a Dutch computer scientist. Its main purpose is to determine the most efficient path from a starting point to a destination in a graph, where the edges connecting the nodes have non-negative weights.

By finding the shortest path, we can optimize travel time, minimize costs, or achieve any other objective that involves reaching a destination using the least amount of resources.

The algorithm maintains a priority queue of nodes, prioritizing those with the shortest tentative distance from the starting node. This helps in efficiently exploring the graph and identifying the shortest paths.

The design and analysis of Dijkstra's algorithm involve carefully considering the efficiency and correctness of the algorithm. Researchers and computer scientists analyze its time complexity, space complexity, and various optimizations to make it perform efficiently on large-scale graphs.

INTRODUCTION :    To find the shortest path between two vertex in a graph We use Dijkstra's algorithm. It is commonly used in navigation systems, network routing, and other applications where finding the shortest path is important.

    Let's say you have a map with several locations and you want to find the shortest path from a starting point to a destination. The Dijkstra's algorithm helps you determine the optimal route.

Let me explain about how it works:

1. Start by assigning a tentative distance value to every vertex in the graph. Initially, set the distance of the starting vertex to 0, and all other vertices to infinity. This represents the current shortest distance from the starting vertex to each vertex.

2. Consider the unvisited vertex with the smallest cost/distance. This vertex becomes the current vertex.

3. For the current vertex examine all of its neighboring vertices (also called adjacent vertex). Calculate the distance from the starting vertex to each neighboring vertex through the current vertex. If this distance is shorter than the previously assigned distance, update the distance value.

4. Once you have visited all the neighbors of the current vertex, mark it as visited. A visited vertex means that the shortest path to that vertex has been found.

5. If the destination node/vertex has been visited, or if the smallest tentative distance among the unvisited vertex is infinity (which means there is no connection between the starting vertex and remaining unvisited vertices), then stop the algorithm. The shortest path has been found, or there is no path to the destination.

6. Otherwise, select the unvisited vertex with the smallest tentative distance and go back to step 3. This vertex becomes the new current vertex, and the process continues until all vertices have been visited or the destination is reached.

7. Finally, you can reconstruct the shortest path by following the chain of nodes from the destination node back to the starting node, using the recorded distances and previously visited nodes.

    By following these steps, Dijkstra's algorithm guarantees to find the shortest path from the starting node to any other node in the graph.

It's important to note that Dijkstra's algorithm works only on graphs with non-negative weights(Costs) on their edges. If there are negative weights, you would need to use other algorithms like the Bellman-Ford algorithm.

Advantages and Disadvantages of Dijkstra's algorithm

Advantages of Dijkstra's algorithm:

1. Guaranteed optimality: It finds the shortest path from a starting node to all other nodes in the graph.
2. Versatility: It can be applied to various scenarios such as navigation systems and network routing.
3. Efficiency for dense graphs: It performs well on graphs with many edges connecting the nodes.

Disadvantages of Dijkstra's algorithm:

1. Non-negative weights: It is designed for graphs with non-negative edge weights and may produce incorrect results for graphs with negative weights.
2. Inefficiency for large graphs: It can be computationally expensive for graphs with a large number of nodes and edges.
3. Lack of heuristics: It does not consider additional heuristics or constraints in the path-finding process.
4. Memory requirements: It requires storing and updating information for each node, leading to high memory usage.

In this way we can understand Dijkstra's algorithm in a simple way!