9.1 Principles of Dijkstra's Algorithm
Dijkstra's Algorithm is an algorithm for finding the shortest paths from a starting vertex to all other vertices in a graph with non-negative edge weights. The algorithm uses a greedy approach, choosing at each step the vertex with the smallest known distance from the starting vertex and updating the distances to neighboring vertices.
Steps of the algorithm:
1. Initialization:
- Set the distance to the starting vertex to 0.
- Set the distance to all other vertices to infinity.
- Create a set of unvisited vertices.
2. Select the current vertex:
- Choose an unvisited vertex with the smallest distance (starting vertex for the first step).
3. Update distances:
- For each neighboring vertex of the current vertex, if a new path through the current vertex is shorter than the known path, update the distance to that vertex.
4. Mark the current vertex as visited:
- Remove the current vertex from the set of unvisited vertices.
5. Repeat steps 2-4 until all vertices are visited or the target vertex is reached.
Time and space complexity of Dijkstra's algorithm:
Time complexity:
O((V + E) log V) when using a priority queue (like a Fibonacci heap),
where V is the number of vertices, E is the number of edges.
O(V^2) when using a simple list to store distances.
Space complexity:
O(V) for storing distances and predecessors (for path reconstruction).
9.2 Implementation of Dijkstra's Algorithm
The implementation of Dijkstra's algorithm is long, but very simple. I recommend you try to understand it. If it seems confusing — scroll back up and reread the main steps of the algorithm.
Example implementation of Dijkstra's algorithm using a priority queue (heap):
import heapq
def dijkstra(graph, start):
# Initialization
distances = {vertex: float('infinity') for vertex in graph}
distances[start] = 0
priority_queue = [(0, start)]
parents = {vertex: None for vertex in graph}
while priority_queue:
current_distance, current_vertex = heapq.heappop(priority_queue)
# If current distance is greater than recorded, skip vertex
if current_distance > distances[current_vertex]:
continue
# Update distances to neighboring vertices
for neighbor, weight in graph[current_vertex].items():
distance = current_distance + weight
# If a shorter path to the neighboring vertex is found
if distance < distances[neighbor]:
distances[neighbor] = distance
parents[neighbor] = current_vertex
heapq.heappush(priority_queue, (distance, neighbor))
return distances, parents
# Example usage:
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
start_vertex = 'A'
distances, parents = dijkstra(graph, start_vertex)
print("Shortest distances from the starting vertex:", distances)
print("Predecessors for path reconstruction:", parents)
Output:
Shortest distances from the starting vertex: {'A': 0, 'B': 1, 'C': 3, 'D': 4}
Predecessors for path reconstruction: {'A': None, 'B': 'A', 'C': 'B', 'D': 'C'}
9.3 Examples of problems solved using Dijkstra's Algorithm
Classic examples of problems solved using Dijkstra's Algorithm:
1. Optimization of routes in transport networks
Finding the shortest path between points in a transport network (e.g., between cities).
Application:
Navigation systems like Google Maps use Dijkstra's Algorithm for calculating optimal routes.
2. Delivery route planning
Optimizing routes for delivery services to minimize costs and delivery time.
Application:
Logistics companies use Dijkstra's Algorithm for planning delivery routes and reducing operational costs.
3. Network management
Optimizing packet routing in computer networks for minimizing delays and increasing bandwidth.
Application:
Routing protocols like OSPF (Open Shortest Path First) use Dijkstra's Algorithm for finding shortest paths in networks.
4. Social network analysis
Finding shortest paths and measuring centrality in social graphs (e.g., identifying the most influential users).
Application:
Social platforms analyze connections between users to provide recommendations and analyze network activity.
5. Games and virtual worlds
Pathfinding for characters in game worlds with obstacles and different difficulty levels.
Application:
Game engines use Dijkstra's Algorithm for calculating the movement of characters and objects in virtual worlds.
6. Energy management systems
Optimizing energy distribution in electric grids for minimizing losses and ensuring supply reliability.
Application:
Energy companies use Dijkstra's Algorithm for optimizing energy transmission routes in networks to minimize energy losses and avoid overloads.
Example:
In electrical grids, each node represents a substation, and edges are power lines with different levels of resistance. Dijkstra's Algorithm helps find the path with the least resistance from the energy source to the consumer.
7. Evacuation and route planning systems
Optimizing evacuation routes in buildings or cities for quick and safe exit in emergency situations.
Application:
Architects and engineers use Dijkstra's Algorithm for planning evacuation routes to ensure a safe and quick removal of people from dangerous zones.
Example:
In an apartment building or office, graph nodes represent rooms and corridors, and edges are paths between them. Dijkstra's Algorithm can be used to find the shortest path from any point in the building to the nearest exit.
GO TO FULL VERSION