Dijkstra Algorithm and other techniques for shortest path in Transport

Dijkstra Algorithm and other techniques for shortest path in Transportation Network

START

Index

Historical Introduction

Purpose and Application in Transport Networks

How it Works

A detailed Example

Other techniques

Historical Introduction

In the serene corridors of the 1950s scientific community, a Dutch computer scientist named Edsger W. Dijkstra introduced an algorithm that would fundamentally transform the way we comprehend and navigate vast networks. As a research paper, it might have seemed innocuous at the time, but Dijkstra's creation soon established itself as a cornerstone in the realm of computer science and algorithmic theory.

Purpose and Application in Transport Networks

So, what exactly is Dijkstra's algorithm designed for? At its heart, Dijkstra's algorithm is a pathfinding method, meticulously crafted to find the shortest path between two points in a weighted graph. In the world of transportation, these 'graphs' manifest as intricate webs of roads, rail tracks, and flight routes. Cities or junctions become the nodes, and the paths between them – be they roads, railway lines, or airways – are the edges with 'weights' representing distances or travel times. When it comes to mapping out the most efficient route from, say, New York to Los Angeles, or from London's King's Cross to Edinburgh's Waverley station, Dijkstra’s algorithm is the silent powerhouse working behind the scenes, ensuring passengers reach their destinations in the quickest possible time by analyzing and prioritizing these routes.

How The Algorithm Works

Diving deeper, the essence of Dijkstra's algorithm lies in its iterative approach:

Initialization: Start with a chosen node (the "source") and assign it a tentative distance of 0. Every other node gets a tentative distance of infinity, symbolizing unknown distances. Exploration: Consider the nearest unvisited node. Calculate tentative distances to all its neighboring nodes. If the newly calculated tentative distance to a neighbor is less than its current assigned value, update it. Selection: After considering all neighbors of the current node, mark it as visited. A visited node will not be checked again. The next node to be visited is the one with the smallest tentative distance. Completion: This iterative process continues until all nodes have been visited, ensuring the shortest path to every node has been found from the source.

A Detailed, Concrete Example

Context: Imagine a transportation network connecting four cities: A, B, C, and D. We need to find the shortest route from city A to city D. Graph Representation: Since it's a complete graph, every city is connected to every other city. Let the distances between the cities be represented as: A - B : 10 units A - C : 15 units A - D : 30 units B - C : 5 units B - D : 15 units C - D : 10 units Objective: Find the shortest path from A to D using Dijkstra's algorithm.

10

30

15

15

10

Solution

Initialization

Visit Node A

Visit the next shortest unvisited node, which is B

Push a step to see an explanation

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

Result

Solution

Initialization

• Set the initial node as A.
• Set distance from A to A = 0 (because it's the starting point).
• For all other nodes, set the initial distance to infinity (or a very large number).
• Set the unvisited nodes as A, B, C, and D.

B= 1000

10

A= 0

Visit Node A

Visit the next shortest unvisited node, which is B

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

10

C= 1000

D= 1000

Result

Solution

Initialization

10

A=0

B=10

Visit Node A

• Distance to A is 0

(already set).

• Distance to B from A = 10.
• Distance to C from A = 15.
• Distance to D from A = 30.
• Mark node A as visited.

Visit the next shortest unvisited node, which is B

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

D=30

10

C=15

Result

Solution

Initialization

10

B=10

• Distance to A is 0.
• Distance to B is 10 (already set).
• Distance to C via B = distance to B + B to C = 10 + 5 = 15. Since the current known distance from A to C is also 15, there's no change.
• Distance to D via B = distance to B + B to D = 10 + 15 = 25. This is better than the current known distance from A to D (which is 30), so we update it.
• Mark node B as visited.

Visit Node A

Visit the next shortest unvisited node, which is B

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

C=15

D=25

10

Result

Solution

Initialization

10

B=10

Visit Node A

Visit the next shortest unvisited node, which is B

• Distance to A is 0.
• Distance to B is 10.
• Distance to C is 15 (already set).
• Distance to D via C = distance to C + C to D = 15 + 10 = 25. Since the current known distance from A to D is also 25, there's no change.
• Mark node C as visited.

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

C=15

D=25

10

Result

Solution

Initialization

10

B=10

Visit Node A

Visit the next shortest unvisited node, which is B

• We already have the shortest distance to D calculated as 25 units via node B.
• Mark node D as visited.

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

C=15

D=25

10

Result

Solution

Initialization

10

Visit Node A

Visit the next shortest unvisited node, which is B

The shortest path from A to D is A -> B -> D with a distance of 25 units.

30

15

15

Visit the next shortest unvisited node, which is C

Visit the last unvisited node, D

C=15

D=25

10

Result

Linear and Mixed Programming

For each technique, it's essential to tailor it to the specifics of the transport network in question and the characteristics of the problem. Sometimes, combining multiple techniques (e.g., using linear programming alongside heuristics) can provide faster or more accurate solutions. At the end of the day, the aim is to find the shortest path as efficiently as possible, and whichever technique or combination of techniques accomplishes that best is the one to choose.

Metaheuristics - Ant Colony Optimization (ACO)

Other Techinques

Multi-agent Systems

Network Decomposition

Autonomous Vehicles: If each vehicle is an agent searching for its shortest path in real-time, it could communicate with other vehicles to gather information about traffic and road conditions. For instance, if one vehicle detects a traffic jam or accident on a route, it can inform other vehicles (agents) seeking the shortest path so they can reconsider their paths. Intelligent Traffic Systems: Traffic lights and cameras, acting as agents, can communicate with each other and with vehicles to optimize traffic flow. For example, if a traffic light detects that a route is clear, it could communicate with other lights to prioritize that route, allowing vehicles seeking the shortest path to utilize it.

Geographical Decomposition: Divide the network into subnets based on geographical regions. Determine the shortest routes within each subnet and then join the solutions from the relevant subnets to form a complete path from start to destination. This is especially useful when working with massive networks, as smaller subproblems can be solved and their solutions combined to get the full route.

Shortest Path Model: Use binary variables to represent whether a specific route (or arc) is used or not. The objective function would focus on minimizing the total cost or distance traveled, and the constraints would ensure that the selected path is continuous and connects the two points of interest.

Application to the shortest path: Artificial ants explore the network from the starting point to the destination point. Initially, the ants' choice of routes is largely random, but as they deposit pheromones, shorter or more efficient routes will get reinforced more. Eventually, the path accumulating the most pheromones will tend to be the shortest between the two points.