3 - Pathfinding Algorithms
Pathfinding algorithms are used to find the shortest or optimal path between two points in a graph. These algorithms are essential in various applications, from navigation systems and network routing to artificial intelligence and game development.
Dijkstra's Algorithm
Dijkstra's algorithm finds the shortest path from a source vertex to all other vertices in a weighted graph with non-negative edge weights.
How Dijkstra's Algorithm Works
- Initialize distances of all vertices as infinite and the source vertex as 0.
- Create a priority queue and insert the source vertex with distance 0.
- While the priority queue is not empty: a. Extract the vertex with the minimum distance. b. For each adjacent vertex, if the distance through the current vertex is less than its current distance, update its distance and add it to the priority queue.
Implementation
/// <summary>
/// Represents a weighted graph using an adjacency list representation and provides
/// methods for finding shortest paths using Dijkstra's algorithm.
/// </summary>
public class Graph
{
private readonly int vertices; // Number of vertices
private readonly List<(int vertex, int weight)>[] adjacencyList;
/// <summary>
/// Initializes a new instance of the Graph class with the specified number of vertices.
/// </summary>
/// <param name="vertices">The number of vertices in the graph.</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the number of vertices is negative.
/// </exception>
public Graph(int vertices)
{
if (vertices < 0)
{
throw new ArgumentOutOfRangeException(nameof(vertices), "Number of vertices must be non-negative.");
}
this.vertices = vertices;
adjacencyList = new List<(int, int)>[vertices];
// Initialize each adjacency list
for (int i = 0; i < vertices; i++)
{
adjacencyList[i] = new List<(int, int)>();
}
}
/// <summary>
/// Adds a directed edge from the source vertex to the destination vertex with the specified weight.
/// </summary>
/// <param name="source">The source vertex.</param>
/// <param name="destination">The destination vertex.</param>
/// <param name="weight">The weight (or cost) of the edge.</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when either source or destination is outside the valid range of vertices.
/// </exception>
/// <exception cref="ArgumentException">
/// Thrown when the weight is negative (Dijkstra's algorithm requires non-negative weights).
/// </exception>
public void AddEdge(int source, int destination, int weight)
{
ValidateVertex(source);
ValidateVertex(destination);
if (weight < 0)
{
throw new ArgumentException("Dijkstra's algorithm requires non-negative edge weights.", nameof(weight));
}
adjacencyList[source].Add((destination, weight));
// For undirected graph, uncomment the following line:
// adjacencyList[destination].Add((source, weight));
}
/// <summary>
/// Finds the shortest paths from the source vertex to all other vertices using Dijkstra's algorithm.
/// This implementation uses a priority queue for better performance.
/// </summary>
/// <param name="source">The source vertex.</param>
/// <returns>An array where distance[i] is the shortest distance from source to vertex i.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the source vertex is outside the valid range.
/// </exception>
public int[] Dijkstra(int source)
{
ValidateVertex(source);
// Distance array to store shortest distance from source to each vertex
int[] distance = new int[vertices];
// Initialize all distances as infinite
for (int i = 0; i < vertices; i++)
{
distance[i] = int.MaxValue;
}
// Distance of source vertex from itself is always 0
distance[source] = 0;
// Priority queue to get the vertex with minimum distance
// The priority is the distance value (lower values have higher priority)
PriorityQueue<int, int> priorityQueue = new PriorityQueue<int, int>();
priorityQueue.Enqueue(source, 0);
while (priorityQueue.Count > 0)
{
// Extract the vertex with minimum distance
int currentVertex = priorityQueue.Dequeue();
// Process each adjacent vertex
foreach (var edge in adjacencyList[currentVertex])
{
int adjacentVertex = edge.vertex;
int edgeWeight = edge.weight;
// If we haven't reached the current vertex yet, skip this edge
if (distance[currentVertex] == int.MaxValue)
{
continue;
}
// Calculate the new potential distance to the adjacent vertex
int newDistance = distance[currentVertex] + edgeWeight;
// If the new distance is shorter than the current known distance
if (newDistance < distance[adjacentVertex])
{
// Update the distance
distance[adjacentVertex] = newDistance;
// Add to the priority queue with the new distance as priority
priorityQueue.Enqueue(adjacentVertex, newDistance);
}
}
}
return distance;
}
/// <summary>
/// Finds the shortest paths from the source vertex to all other vertices using Dijkstra's algorithm.
/// This implementation does not use a priority queue and is suitable for environments where
/// PriorityQueue is not available (pre-.NET 6.0).
/// </summary>
/// <param name="source">The source vertex.</param>
/// <returns>An array where distance[i] is the shortest distance from source to vertex i.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the source vertex is outside the valid range.
/// </exception>
public int[] DijkstraWithoutPriorityQueue(int source)
{
ValidateVertex(source);
// Distance array to store shortest distance from source to each vertex
int[] distance = new int[vertices];
// Array to keep track of vertices included in the shortest path tree
bool[] visited = new bool[vertices];
// Initialize all distances as infinite and visited as false
for (int i = 0; i < vertices; i++)
{
distance[i] = int.MaxValue;
visited[i] = false;
}
// Distance of source vertex from itself is always 0
distance[source] = 0;
// Find shortest path for all vertices
for (int count = 0; count < vertices - 1; count++)
{
// Pick the minimum distance vertex from the set of vertices not yet processed
int currentVertex = MinimumDistance(distance, visited);
// If we couldn't find a valid vertex (all remaining vertices are unreachable)
if (currentVertex == -1)
{
break;
}
// Mark the picked vertex as processed
visited[currentVertex] = true;
// Update distance values of adjacent vertices
foreach (var edge in adjacencyList[currentVertex])
{
int adjacentVertex = edge.vertex;
int edgeWeight = edge.weight;
// Update distance[adjacentVertex] only if:
// 1. It's not visited yet
// 2. There is a path from source to currentVertex
// 3. The path through currentVertex to adjacentVertex is shorter than the current distance
if (!visited[adjacentVertex] &&
distance[currentVertex] != int.MaxValue &&
distance[currentVertex] + edgeWeight < distance[adjacentVertex])
{
distance[adjacentVertex] = distance[currentVertex] + edgeWeight;
}
}
}
return distance;
}
/// <summary>
/// Finds the vertex with the minimum distance value from the set of vertices not yet included in the shortest path tree.
/// </summary>
/// <param name="distance">Array of distances from the source vertex.</param>
/// <param name="visited">Array indicating which vertices have been visited.</param>
/// <returns>The index of the vertex with the minimum distance, or -1 if all remaining vertices are unreachable.</returns>
private int MinimumDistance(int[] distance, bool[] visited)
{
int min = int.MaxValue;
int minIndex = -1;
// Find the vertex with minimum distance from the set of vertices not yet processed
for (int v = 0; v < vertices; v++)
{
if (!visited[v] && distance[v] <= min)
{
min = distance[v];
minIndex = v;
}
}
return minIndex;
}
/// <summary>
/// Finds the shortest path from the source vertex to the destination vertex using Dijkstra's algorithm.
/// </summary>
/// <param name="source">The source vertex.</param>
/// <param name="destination">The destination vertex.</param>
/// <returns>A list representing the shortest path from source to destination, or an empty list if no path exists.</returns>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when either source or destination is outside the valid range.
/// </exception>
public List<int> GetShortestPath(int source, int destination)
{
ValidateVertex(source);
ValidateVertex(destination);
// If source and destination are the same, return a path with just the source
if (source == destination)
{
return new List<int> { source };
}
// Distance array to store shortest distance from source to each vertex
int[] distance = new int[vertices];
// Array to store the previous vertex in the shortest path
int[] previous = new int[vertices];
// Initialize all distances as infinite and previous as -1 (no previous vertex)
for (int i = 0; i < vertices; i++)
{
distance[i] = int.MaxValue;
previous[i] = -1;
}
// Distance of source vertex from itself is always 0
distance[source] = 0;
// Priority queue to get the vertex with minimum distance
PriorityQueue<int, int> priorityQueue = new PriorityQueue<int, int>();
priorityQueue.Enqueue(source, 0);
// Flag to indicate if destination is found
bool foundDestination = false;
while (priorityQueue.Count > 0 && !foundDestination)
{
// Extract the vertex with minimum distance
int currentVertex = priorityQueue.Dequeue();
// If we've reached the destination, we can stop
if (currentVertex == destination)
{
foundDestination = true;
break;
}
// If the current distance is already infinity, we can't improve it
if (distance[currentVertex] == int.MaxValue)
{
continue;
}
// Process each adjacent vertex
foreach (var edge in adjacencyList[currentVertex])
{
int adjacentVertex = edge.vertex;
int edgeWeight = edge.weight;
// Calculate the new potential distance to the adjacent vertex
int newDistance = distance[currentVertex] + edgeWeight;
// If the new distance is shorter than the current known distance
if (newDistance < distance[adjacentVertex])
{
// Update the distance and previous vertex
distance[adjacentVertex] = newDistance;
previous[adjacentVertex] = currentVertex;
// Add to the priority queue with the new distance as priority
priorityQueue.Enqueue(adjacentVertex, newDistance);
}
}
}
// If destination was not found or is unreachable, return an empty path
if (!foundDestination || distance[destination] == int.MaxValue)
{
return new List<int>();
}
// Reconstruct the path from destination to source
List<int> path = new List<int>();
for (int at = destination; at != -1; at = previous[at])
{
path.Add(at);
}
// Reverse to get path from source to destination
path.Reverse();
return path;
}
/// <summary>
/// Gets the number of vertices in the graph.
/// </summary>
public int VertexCount => vertices;
/// <summary>
/// Validates that a vertex index is within the valid range.
/// </summary>
/// <param name="vertex">The vertex index to validate.</param>
/// <exception cref="ArgumentOutOfRangeException">
/// Thrown when the vertex is outside the valid range.
/// </exception>
private void ValidateVertex(int vertex)
{
if (vertex < 0 || vertex >= vertices)
{
throw new ArgumentOutOfRangeException(nameof(vertex),
$"Vertex must be between 0 and {vertices - 1}.");
}
}
}
Time and Space Complexity
- Time Complexity:
- With binary heap: O((V + E) log V) where V is the number of vertices and E is the number of edges.
- With array implementation: O(V²)
- Space Complexity: O(V) for the distance array and priority queue.
Applications
- GPS Navigation: Finding the shortest route between locations.
- Network Routing: Determining the most efficient path for data packets.
- Flight Scheduling: Finding the shortest or cheapest routes.
- Robotics: Planning optimal paths for robots.
- Telecommunications: Routing calls through a network.
Bellman-Ford Algorithm
The Bellman-Ford algorithm finds the shortest path from a source vertex to all other vertices, even in graphs with negative edge weights (but no negative cycles).
How Bellman-Ford Algorithm Works
- Initialize distances of all vertices as infinite and the source vertex as 0.
- Relax all edges V-1 times, where V is the number of vertices.
- Check for negative weight cycles by attempting to relax edges one more time.
Implementation
public class Edge
{
public int Source { get; set; }
public int Destination { get; set; }
public int Weight { get; set; }
public Edge(int source, int destination, int weight)
{
Source = source;
Destination = destination;
Weight = weight;
}
}
public class GraphEdgeList
{
private int V; // Number of vertices
private List<Edge> edges;
public GraphEdgeList(int v)
{
V = v;
edges = new List<Edge>();
}
public void AddEdge(int source, int destination, int weight)
{
edges.Add(new Edge(source, destination, weight));
}
public (int[] distance, bool hasNegativeCycle) BellmanFord(int source)
{
// Initialize distances
int[] distance = new int[V];
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
}
distance[source] = 0;
// Relax all edges V-1 times
for (int i = 1; i < V; i++)
{
foreach (Edge edge in edges)
{
int u = edge.Source;
int v = edge.Destination;
int weight = edge.Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
{
distance[v] = distance[u] + weight;
}
}
}
// Check for negative weight cycles
bool hasNegativeCycle = false;
foreach (Edge edge in edges)
{
int u = edge.Source;
int v = edge.Destination;
int weight = edge.Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
{
hasNegativeCycle = true;
break;
}
}
return (distance, hasNegativeCycle);
}
// Reconstruct the shortest path from source to destination
public List<int> GetShortestPath(int source, int destination)
{
int[] distance = new int[V];
int[] previous = new int[V];
for (int i = 0; i < V; i++)
{
distance[i] = int.MaxValue;
previous[i] = -1;
}
distance[source] = 0;
// Relax all edges V-1 times
for (int i = 1; i < V; i++)
{
foreach (Edge edge in edges)
{
int u = edge.Source;
int v = edge.Destination;
int weight = edge.Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
{
distance[v] = distance[u] + weight;
previous[v] = u;
}
}
}
// Check for negative weight cycles
foreach (Edge edge in edges)
{
int u = edge.Source;
int v = edge.Destination;
int weight = edge.Weight;
if (distance[u] != int.MaxValue && distance[u] + weight < distance[v])
{
throw new InvalidOperationException("Graph contains negative weight cycle");
}
}
// Reconstruct the path
List<int> path = new List<int>();
if (distance[destination] == int.MaxValue)
return path; // No path exists
for (int at = destination; at != -1; at = previous[at])
{
path.Add(at);
}
path.Reverse(); // Reverse to get path from source to destination
return path;
}
}
Time and Space Complexity
- Time Complexity: O(V × E) where V is the number of vertices and E is the number of edges.
- Space Complexity: O(V) for the distance array.
Applications
- Network Routing: When negative weights are present.
- Currency Exchange: Detecting arbitrage opportunities.
- Traffic Engineering: Modeling networks with both positive and negative constraints.
- Distributed Systems: Computing shortest paths in systems with varying costs.
Floyd-Warshall Algorithm
The Floyd-Warshall algorithm finds the shortest paths between all pairs of vertices in a weighted graph, including those with negative edge weights (but no negative cycles).
How Floyd-Warshall Algorithm Works
- Initialize the distance matrix with direct edge weights.
- For each vertex k as an intermediate vertex, update the shortest path between every pair of vertices i and j.
Implementation
public class GraphMatrix
{
private int V; // Number of vertices
private int[,] graph; // Adjacency matrix
public GraphMatrix(int v)
{
V = v;
graph = new int[v, v];
// Initialize the graph with infinity for all non-adjacent vertices
for (int i = 0; i < v; i++)
{
for (int j = 0; j < v; j++)
{
if (i == j)
graph[i, j] = 0;
else
graph[i, j] = int.MaxValue;
}
}
}
public void AddEdge(int u, int v, int weight)
{
graph[u, v] = weight;
// For undirected graph
// graph[v, u] = weight;
}
public int[,] FloydWarshall()
{
int[,] distance = new int[V, V];
// Initialize distance matrix same as the graph
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
distance[i, j] = graph[i, j];
}
}
// Consider each vertex as an intermediate vertex
for (int k = 0; k < V; k++)
{
// Pick all vertices as source one by one
for (int i = 0; i < V; i++)
{
// Pick all vertices as destination
for (int j = 0; j < V; j++)
{
// If vertex k is on the shortest path from i to j,
// update the value of distance[i, j]
if (distance[i, k] != int.MaxValue && distance[k, j] != int.MaxValue &&
distance[i, k] + distance[k, j] < distance[i, j])
{
distance[i, j] = distance[i, k] + distance[k, j];
}
}
}
}
// Check for negative cycles
for (int i = 0; i < V; i++)
{
if (distance[i, i] < 0)
{
throw new InvalidOperationException("Graph contains negative weight cycle");
}
}
return distance;
}
// Reconstruct the shortest path from source to destination
public List<int> GetShortestPath(int source, int destination)
{
int[,] distance = new int[V, V];
int[,] next = new int[V, V];
// Initialize distance matrix and next matrix
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
distance[i, j] = graph[i, j];
if (i == j || graph[i, j] == int.MaxValue)
next[i, j] = -1;
else
next[i, j] = j;
}
}
// Floyd-Warshall algorithm with path reconstruction
for (int k = 0; k < V; k++)
{
for (int i = 0; i < V; i++)
{
for (int j = 0; j < V; j++)
{
if (distance[i, k] != int.MaxValue && distance[k, j] != int.MaxValue &&
distance[i, k] + distance[k, j] < distance[i, j])
{
distance[i, j] = distance[i, k] + distance[k, j];
next[i, j] = next[i, k];
}
}
}
}
// Reconstruct the path
List<int> path = new List<int>();
if (distance[source, destination] == int.MaxValue)
return path; // No path exists
int at = source;
path.Add(at);
while (at != destination)
{
at = next[at, destination];
if (at == -1)
return new List<int>(); // No path exists
path.Add(at);
}
return path;
}
}
Time and Space Complexity
- Time Complexity: O(V³) where V is the number of vertices.
- Space Complexity: O(V²) for the distance matrix.
Applications
- All-Pairs Shortest Paths: Finding shortest paths between all pairs of vertices.
- Network Analysis: Analyzing the connectivity of all nodes in a network.
- Traffic Engineering: Computing shortest paths for all origin-destination pairs.
- Transitive Closure: Determining if a path exists between any two vertices.
A* Search Algorithm
A* (pronounced "A-star") is an informed search algorithm that finds the shortest path from a start node to a goal node using a heuristic function to guide the search.
How A* Search Works
- Initialize the open list with the start node and the closed list as empty.
- While the open list is not empty:
a. Find the node with the lowest f(n) = g(n) + h(n) in the open list, where:
- g(n) is the cost from the start node to the current node.
- h(n) is the heuristic estimate of the cost from the current node to the goal. b. If the current node is the goal, reconstruct and return the path. c. Move the current node from the open list to the closed list. d. For each neighbor of the current node:
- If it's in the closed list, skip it.
- Calculate its tentative g score.
- If it's not in the open list or the tentative g score is better, update its scores and add it to the open list.
Implementation
public class Node : IComparable<Node>
{
public int X { get; set; }
public int Y { get; set; }
public int G { get; set; } // Cost from start node
public int H { get; set; } // Heuristic cost to goal
public int F => G + H; // Total cost
public Node Parent { get; set; }
public Node(int x, int y)
{
X = x;
Y = y;
G = 0;
H = 0;
Parent = null;
}
public int CompareTo(Node other)
{
return F.CompareTo(other.F);
}
public override bool Equals(object obj)
{
if (obj is Node other)
{
return X == other.X && Y == other.Y;
}
return false;
}
public override int GetHashCode()
{
return X.GetHashCode() ^ Y.GetHashCode();
}
}
public class AStar
{
private int[,] grid;
private int rows;
private int cols;
private int[] dx = { -1, 0, 1, 0, -1, -1, 1, 1 }; // 8-directional movement
private int[] dy = { 0, 1, 0, -1, -1, 1, -1, 1 };
public AStar(int[,] grid)
{
this.grid = grid;
rows = grid.GetLength(0);
cols = grid.GetLength(1);
}
public List<Node> FindPath(int startX, int startY, int goalX, int goalY)
{
// Check if start or goal is out of bounds or blocked
if (startX < 0 || startX >= rows || startY < 0 || startY >= cols ||
goalX < 0 || goalX >= rows || goalY < 0 || goalY >= cols ||
grid[startX, startY] == 1 || grid[goalX, goalY] == 1)
{
return new List<Node>();
}
Node startNode = new Node(startX, startY);
Node goalNode = new Node(goalX, goalY);
// Calculate heuristic for start node
startNode.H = CalculateHeuristic(startNode, goalNode);
PriorityQueue<Node, int> openList = new PriorityQueue<Node, int>();
HashSet<(int, int)> closedSet = new HashSet<(int, int)>();
Dictionary<(int, int), Node> openDict = new Dictionary<(int, int), Node>();
openList.Enqueue(startNode, startNode.F);
openDict.Add((startNode.X, startNode.Y), startNode);
while (openList.Count > 0)
{
Node current = openList.Dequeue();
openDict.Remove((current.X, current.Y));
// If we've reached the goal, reconstruct and return the path
if (current.X == goalNode.X && current.Y == goalNode.Y)
{
return ReconstructPath(current);
}
closedSet.Add((current.X, current.Y));
// Check all neighbors
for (int i = 0; i < dx.Length; i++)
{
int newX = current.X + dx[i];
int newY = current.Y + dy[i];
// Skip if out of bounds or blocked
if (newX < 0 || newX >= rows || newY < 0 || newY >= cols ||
grid[newX, newY] == 1 || closedSet.Contains((newX, newY)))
{
continue;
}
// Calculate movement cost (diagonal movement costs more)
int movementCost = (i < 4) ? 10 : 14; // 10 for cardinal, 14 for diagonal (√2 * 10)
int tentativeG = current.G + movementCost;
Node neighbor = new Node(newX, newY)
{
G = tentativeG,
H = CalculateHeuristic(new Node(newX, newY), goalNode),
Parent = current
};
if (openDict.TryGetValue((newX, newY), out Node existingNode))
{
// If this path is better than the previous one
if (tentativeG < existingNode.G)
{
// Update the node
existingNode.G = tentativeG;
existingNode.Parent = current;
// Re-add to priority queue with updated priority
openList.Enqueue(existingNode, existingNode.F);
}
}
else
{
// Add to open list
openList.Enqueue(neighbor, neighbor.F);
openDict.Add((newX, newY), neighbor);
}
}
}
// No path found
return new List<Node>();
}
private int CalculateHeuristic(Node a, Node b)
{
// Manhattan distance
// return 10 * (Math.Abs(a.X - b.X) + Math.Abs(a.Y - b.Y));
// Diagonal distance
int dx = Math.Abs(a.X - b.X);
int dy = Math.Abs(a.Y - b.Y);
return 10 * (dx + dy) + (14 - 2 * 10) * Math.Min(dx, dy);
}
private List<Node> ReconstructPath(Node node)
{
List<Node> path = new List<Node>();
while (node != null)
{
path.Add(node);
node = node.Parent;
}
path.Reverse();
return path;
}
}
Time and Space Complexity
- Time Complexity: O(E) where E is the number of edges, but in practice, the heuristic significantly reduces the search space.
- Space Complexity: O(V) where V is the number of vertices.
Applications
- Video Games: Pathfinding for NPCs and AI characters.
- Robotics: Planning efficient paths for robots.
- GPS Navigation: Finding optimal routes with real-time traffic data.
- Puzzle Solving: Solving problems like the 15-puzzle or Rubik's cube.
- Network Routing: Finding paths that balance multiple constraints.
Comparison of Pathfinding Algorithms
| Algorithm | Time Complexity | Space Complexity | Handles Negative Weights | All-Pairs | Heuristic-Based | Best Use Case |
|---|---|---|---|---|---|---|
| Dijkstra | O((V + E) log V) | O(V) | No | No | No | Single-source shortest paths with non-negative weights |
| Bellman-Ford | O(V × E) | O(V) | Yes | No | No | Single-source shortest paths with possible negative weights |
| Floyd-Warshall | O(V³) | O(V²) | Yes | Yes | No | All-pairs shortest paths in dense graphs |
| A* | O(E) (worst case) | O(V) | No | No | Yes | Finding shortest path with additional information about the goal |
Advanced Pathfinding Techniques
Bidirectional Search
Bidirectional search runs two simultaneous searches: one from the source and one from the destination, terminating when they meet.
public List<int> BidirectionalDijkstra(int source, int destination)
{
// Forward search from source
int[] distanceForward = new int[V];
int[] previousForward = new int[V];
// Backward search from destination
int[] distanceBackward = new int[V];
int[] previousBackward = new int[V];
// Initialize
for (int i = 0; i < V; i++)
{
distanceForward[i] = int.MaxValue;
previousForward[i] = -1;
distanceBackward[i] = int.MaxValue;
previousBackward[i] = -1;
}
distanceForward[source] = 0;
distanceBackward[destination] = 0;
PriorityQueue<int, int> pqForward = new PriorityQueue<int, int>();
PriorityQueue<int, int> pqBackward = new PriorityQueue<int, int>();
pqForward.Enqueue(source, 0);
pqBackward.Enqueue(destination, 0);
HashSet<int> visitedForward = new HashSet<int>();
HashSet<int> visitedBackward = new HashSet<int>();
int meetingPoint = -1;
int shortestDistance = int.MaxValue;
while (pqForward.Count > 0 && pqBackward.Count > 0)
{
// Forward step
int u = pqForward.Dequeue();
visitedForward.Add(u);
if (distanceForward[u] > shortestDistance)
break;
if (visitedBackward.Contains(u))
{
int distance = distanceForward[u] + distanceBackward[u];
if (distance < shortestDistance)
{
shortestDistance = distance;
meetingPoint = u;
}
}
foreach (var edge in adjacencyList[u])
{
int v = edge.vertex;
int weight = edge.weight;
if (distanceForward[u] != int.MaxValue && distanceForward[u] + weight < distanceForward[v])
{
distanceForward[v] = distanceForward[u] + weight;
previousForward[v] = u;
pqForward.Enqueue(v, distanceForward[v]);
}
}
// Backward step
u = pqBackward.Dequeue();
visitedBackward.Add(u);
if (distanceBackward[u] > shortestDistance)
break;
if (visitedForward.Contains(u))
{
int distance = distanceForward[u] + distanceBackward[u];
if (distance < shortestDistance)
{
shortestDistance = distance;
meetingPoint = u;
}
}
foreach (var edge in adjacencyList[u])
{
int v = edge.vertex;
int weight = edge.weight;
if (distanceBackward[u] != int.MaxValue && distanceBackward[u] + weight < distanceBackward[v])
{
distanceBackward[v] = distanceBackward[u] + weight;
previousBackward[v] = u;
pqBackward.Enqueue(v, distanceBackward[v]);
}
}
}
// Reconstruct the path
if (meetingPoint == -1)
return new List<int>(); // No path exists
List<int> pathForward = new List<int>();
for (int at = meetingPoint; at != -1; at = previousForward[at])
{
pathForward.Add(at);
}
pathForward.Reverse();
List<int> pathBackward = new List<int>();
for (int at = previousBackward[meetingPoint]; at != -1; at = previousBackward[at])
{
pathBackward.Add(at);
}
// Combine the paths
List<int> path = new List<int>(pathForward);
path.AddRange(pathBackward);
return path;
}
Contraction Hierarchies
Contraction Hierarchies is a preprocessing-based technique that significantly speeds up shortest path queries by adding shortcuts to the graph.
Multi-Level Dijkstra
Multi-Level Dijkstra uses a hierarchical approach to speed up pathfinding in large graphs by precomputing shortcuts at different levels of abstraction.
Practical Applications and Examples
GPS Navigation
public class GPSNavigator
{
private Graph roadNetwork;
public GPSNavigator(Graph roadNetwork)
{
this.roadNetwork = roadNetwork;
}
public List<int> FindFastestRoute(int startLocation, int endLocation)
{
return roadNetwork.GetShortestPath(startLocation, endLocation);
}
public List<int> FindAlternativeRoute(int startLocation, int endLocation, List<int> mainRoute, double diversityFactor)
{
// Increase weights of edges in the main route to encourage diversity
foreach (int vertex in mainRoute)
{
// Increase weights of edges connected to this vertex
// Implementation depends on the graph representation
}
// Find a new route with the modified weights
List<int> alternativeRoute = roadNetwork.GetShortestPath(startLocation, endLocation);
// Restore original weights
// ...
return alternativeRoute;
}
}
Game AI Pathfinding
public class GameAI
{
private AStar pathfinder;
private int[,] gameMap;
public GameAI(int[,] gameMap)
{
this.gameMap = gameMap;
pathfinder = new AStar(gameMap);
}
public List<Node> MoveToTarget(int startX, int startY, int targetX, int targetY)
{
return pathfinder.FindPath(startX, startY, targetX, targetY);
}
public void UpdateMap(int x, int y, int value)
{
gameMap[x, y] = value;
// Recreate pathfinder with updated map
pathfinder = new AStar(gameMap);
}
}
Network Routing
public class NetworkRouter
{
private Graph network;
public NetworkRouter(Graph network)
{
this.network = network;
}
public List<int> RoutePacket(int sourceNode, int destinationNode)
{
return network.GetShortestPath(sourceNode, destinationNode);
}
public void HandleLinkFailure(int node1, int node2)
{
// Set the weight of the failed link to infinity
// Implementation depends on the graph representation
// Recalculate routes affected by the failure
// ...
}
public void BalanceLoad()
{
// Adjust weights based on current network load
// ...
// Recalculate routes to balance the load
// ...
}
}
Best Practices and Optimization
Choosing the Right Algorithm
-
Use Dijkstra's Algorithm when:
- You need the shortest path from a single source to one or all other vertices.
- All edge weights are non-negative.
- The graph is relatively sparse.
-
Use Bellman-Ford Algorithm when:
- You need the shortest path from a single source to all other vertices.
- The graph may have negative edge weights.
- You need to detect negative cycles.
-
Use Floyd-Warshall Algorithm when:
- You need the shortest paths between all pairs of vertices.
- The graph is dense.
- The graph may have negative edge weights.
-
Use A Search Algorithm* when:
- You need the shortest path between two specific vertices.
- You have additional information (heuristic) about the goal.
- Performance is critical.
Optimizing Pathfinding Algorithms
- Use Appropriate Data Structures: Choose efficient priority queue implementations for Dijkstra's and A* algorithms.
- Precompute and Cache: For static graphs, precompute and store paths or distances.
- Hierarchical Approaches: Use techniques like contraction hierarchies for large graphs.
- Bidirectional Search: Implement bidirectional search for faster path finding between two points.
- Heuristic Tuning: For A*, carefully design and tune the heuristic function.
- Early Termination: Stop the algorithm once the destination is reached (for single-target searches).
- Parallel Processing: For large graphs, consider parallel implementations of pathfinding algorithms.
Conclusion
Pathfinding algorithms are essential tools for solving a wide range of problems involving optimal paths in graphs. By understanding the characteristics, strengths, and limitations of each algorithm, you can choose the most appropriate one for your specific requirements.
Whether you're developing a navigation system, a network router, or a game AI, these algorithms provide the foundation for efficient path discovery and optimization. The advanced techniques and optimizations discussed can help you tackle even the most challenging pathfinding problems in large and complex graphs.