27.1.4. Week- 04

So, now let us analyze Dijkstra’s algorithm for the single source shortest path problem.

Dijkstra’s algorithm is designed to solve the single-source shortest path problem in a graph. This means it finds the shortest paths from a specified starting vertex (source) to all other vertices in the graph. The algorithm operates by maintaining a priority queue of vertices based on their current known shortest distance from the source.

Imagine navigating through city streets from a starting point. Each intersection can be thought of as a vertex, and the roads connecting them represent edges with distances. Dijkstra’s algorithm helps determine the quickest route to all other intersections from your starting point.

Initially nothing is visited and we do not know any distance to any vertex. So, we assume all distances are infinity. When we start at the source vertex, we set its distance to 0.

At the beginning of Dijkstra’s algorithm, no vertices have been 'visited,' and their distances are unknown. Hence, all distances are initialized to infinity (a concept that represents an undefined or very large number). The source vertex’s distance is set to 0 because the shortest path from the source to itself is always zero.

Think of this as setting out on a journey. You haven't yet visited any destinations, and since you don’t know how far each location is, you consider all distances to be infinity. However, your starting point is where you are now, which has zero distance.

We repeatedly pick the first vertex which is not burnt and has the minimum distance among those which are not burnt.

Throughout the iteration of the algorithm, the next vertex to be processed is chosen based on its distance from the source. The algorithm looks for the vertex that has the smallest known distance and has not yet been visited (or 'burnt'). This ensures that we always extend our shortest path from the closest vertex known.

Imagine you are shopping with a limited amount of fuel. Each shop (vertex) has a distance from your starting point (the source). You would choose to visit the closest shop first to save time and fuel, ensuring that you are making the most efficient choices at each step.

The key to establishing correctness is an invariant. At each iteration, burnt vertices are correctly solved. If we assume this invariant is true, then when we add a new vertex, its distance cannot be smaller than what we computed.

To prove that Dijkstra's algorithm is correct, we maintain an invariant that states all distances calculated for burnt vertices are indeed the shortest paths from the source. When extending the set of burnt vertices by including a new vertex, the algorithm ensures that no shorter path to this newly added vertex exists based on previously burnt vertices.

Consider this invariant like confirming that a finished puzzle piece accurately fits into its spot. Once you place a piece (or 'burn' a vertex'), you can confidently say it belongs there because all the pieces around it are correctly placed.

We saw that the overall complexity becomes O(n + m log n), where n is the number of vertices and m is the number of edges in the graph.

The complexity of Dijkstra’s algorithm depends on how the graph is represented and how we manage the priority queue. If we use simple data structures, the algorithm can take O(n²) time, but using efficient structures (like heaps) brings the time down to O(n + m log n), which is much more efficient for larger graphs.

Think of this complexity like planning a large event. If you manage it manually as a checklist, it takes longer (O(n²)). But if you use a dedicated software program that organizes everything for you, it significantly reduces the time needed to coordinate (O(n + m log n)).

Dijkstra's algorithm makes a crucial assumption that there are no negative cost edges. If there are negative edges, it may lead to incorrect paths.

Dijkstra's algorithm assumes all edge weights are non-negative, meaning you cannot lose 'distance' or 'gain' distance along a path. When negative weight edges are present, the assumptions of the algorithm break down. This may lead to scenarios where we find shorter paths erroneously because the algorithm only considers local information.

Consider traveling where toll roads charge you money (positive edges), while some paths may seem free (negative edges in terms of cost). If we consider these 'free' paths without understanding they might lead to detours, we might think we have found the best route when we really haven't.

--