Dijkstra's Algorithm Explained

Dijkstra's Algorithm

• Given a weighted graph G = (V, E, w) and a starting node s ∈ V, Dijkstra's algorithm finds the shortest paths from s to all other nodes in V.
• Distances to all nodes are initialized to infinity, except for the starting node s, whose distance is set to 0.
• A priority queue (e.g., Min-Heap) manages the nodes based on their current distance.
• It iteratively selects the node u with the smallest distance from the priority queue.
• Updates the distances to the neighbors v of u if the path from s via u to v is shorter than the current distance of v.

Dijkstra Pseudocode

• Initialize distances to infinity for all nodes, except the start node.
• Set the start node's distance to zero.
• While the priority queue is not empty:
  • Select node with smallest known distance.
  • Update neighbors' distances if a shorter path is found.

Dijkstra Example Graph

• Graph with nodes A, B, C, D, E.
• Edge weights:
  • A -> B: 4
  • A -> C: 2
  • B -> C: 1
  • B -> D: 5
  • C -> D: 8
  • C -> E: 10
  • D -> E: 2
• Starting node: A

Dijkstra Example Initialization

• dist[A] = 0, dist[B] = ∞, dist[C] = ∞, dist[D] = ∞, dist[E] = ∞
• priority_queue = {A}

Dijkstra Example Iteration 1

• u = A
• Neighbors of A: B, C
• dist[B] = 4, dist[C] = 2
• priority_queue = {C, B}

Dijkstra Example Iteration 2

• u = C
• Neighbors of C: B, D, E
• dist[B] = 3 (updated), dist[D] = 10, dist[E] = 12
• priority_queue = {B, D, E}

Dijkstra Example Iteration 3

• u = B
• Neighbors of B: D
• dist[D] = 8 (updated)
• priority_queue = {D, E}

Dijkstra Example Iteration 4

• u = D
• Neighbors of D: E
• dist[E] = 10 (updated)
• priority_queue = {E}

Dijkstra Example Iteration 5

• u = E
• No neighbors to update.
• priority_queue = {}

Dijkstra Example Results

• Shortest distances from A to all nodes:
  • A: 0
  • B: 3
  • C: 2
  • D: 8
  • E: 10

Dijkstra Properties

• Typical runtime of $O((|V| + |E|) \log |V|)$ using a priority queue.
• With Fibonacci-Heaps runtime is $O(|E| + |V| \log |V|)$.
• Works only for graphs with non-negative edge weights.
• For graphs with negative edge weights, the Bellman-Ford algorithm must be used.
• Dijkstra's algorithm makes locally optimal decisions, and selects the node with the smallest current distance.
• Calculates the shortest paths from one start node to all other nodes.

Dijkstra Applications

• Route planning in navigation systems.
• Routing data packets in computer networks.
• Optimization of supply chains and transport routes.
• Pathfinding in games and simulations.

Bernoulli's Principle

• An increase in the speed of a fluid occurs simultaneously with a decrease in pressure or a decrease in the fluid's potential energy.

Bernoulli's Equation

• $P_1 + \frac{1}{2} \rho v_1^2 + \rho g h_1 = P_2 + \frac{1}{2} \rho v_2^2 + \rho g h_2$
  • P = absolute pressure of the fluid
  • v = fluid velocity
  • h = height of the container
  • ρ = density

Simplified Bernoulli's Equation (constant height)

• $P_1 + \frac{1}{2} \rho v_1^2 = P_2 + \frac{1}{2} \rho v_2^2$

Venturi Effect

• The reduction in fluid pressure that results when a fluid flows through a constricted section of a pipe.

Lift

• An upward force on an object that occurs because of the object's motion through a fluid.

Lift Equation

• $L = \frac{1}{2} \rho v^2 A C_L$
  • L = lift force
  • ρ = fluid density
  • v = velocity
  • A = surface area
  • $C_L$ = lift coefficient