Dynamic routing algorithms for transportation networks using C++

12 Oct 2023

Transportation networks play a crucial role in our daily lives, enabling the efficient movement of people and goods. To optimize the use of these networks, dynamic routing algorithms are employed to determine the most optimal paths based on real-time data. In this blog post, we will explore dynamic routing algorithms for transportation networks using C++.

Introduction to Dynamic Routing
Dijkstra’s Algorithm
A* Algorithm
Bellman-Ford Algorithm
Conclusion
Resources

1. Introduction to Dynamic Routing

Dynamic routing algorithms are used to find the shortest or most efficient path between two points in a network. Unlike static routing algorithms that consider a fixed network topology, dynamic routing algorithms take into account real-time traffic conditions, road closures, and other dynamic factors to determine the optimal path.

2. Dijkstra’s Algorithm

Dijkstra’s algorithm is a widely used dynamic routing algorithm that finds the shortest path between two nodes in a graph. It works by iteratively exploring the nodes starting from the source node, assigning tentative costs to each node, and updating them if a shorter path is found. Dijkstra’s algorithm guarantees finding the shortest path but is computationally expensive for large graphs.

// Example code for Dijkstra's Algorithm
#include <iostream>
#include <vector>
#include <queue>

struct Edge {
    int destination;
    int weight;
};

std::vector<int> Dijkstra(std::vector<std::vector<Edge>>& graph, int source) {
    std::vector<int> distances(graph.size(), INT_MAX);
    
    distances[source] = 0;
    std::priority_queue<std::pair<int, int>, std::vector<std::pair<int, int>>, std::greater<std::pair<int, int>>> pq;
    pq.push({0, source});
    
    while (!pq.empty()) {
        int node = pq.top().second;
        int distance = pq.top().first;
        pq.pop();
        
        if (distance > distances[node]) {
            continue;
        }
        
        for (const Edge& edge : graph[node]) {
            int newDistance = distances[node] + edge.weight;
            
            if (newDistance < distances[edge.destination]) {
                distances[edge.destination] = newDistance;
                pq.push({newDistance, edge.destination});
            }
        }
    }
    
    return distances;
}

3. A* Algorithm

The A* algorithm is another popular choice for dynamic routing in transportation networks. It combines aspects of Dijkstra’s algorithm and informed search by considering both the cost to reach a node and an estimate of the remaining cost to the destination. This heuristic estimation is typically based on factors like distance or travel time. A* algorithm provides optimal and efficient paths in many scenarios.

// Example code for A* Algorithm
#include <iostream>
#include <vector>
#include <queue>

struct Node {
    int id;
    int gScore;
    int hScore;
    Node* parent;
};

struct Edge {
    int destination;
    int weight;
};

std::vector<int> AStar(std::vector<std::vector<Edge>>& graph, int source, int destination) {
    std::vector<int> distances(graph.size(), INT_MAX);
    std::vector<int> path;
    
    std::priority_queue<Node*, std::vector<Node*>, CompareNodes> openList;
    std::vector<bool> visited(graph.size(), false);
    
    distances[source] = 0;
    Node* start = new Node{source, 0, 0, nullptr};
    openList.push(start);
    
    while (!openList.empty()) {
        Node* current = openList.top();
        openList.pop();
        
        if (visited[current->id]) {
            continue;
        }
        
        visited[current->id] = true;
        
        if (current->id == destination) {
            Node* node = current;
            
            while (node) {
                path.push_back(node->id);
                node = node->parent;
            }
            
            std::reverse(path.begin(), path.end());
            return path;
        }
        
        for (const Edge& edge : graph[current->id]) {
            int newDistance = current->gScore + edge.weight;
            
            if (newDistance < distances[edge.destination]) {
                Node* newNode = new Node{edge.destination, newDistance, 0, current};
                openList.push(newNode);
                distances[edge.destination] = newDistance;
            }
        }
    }
    
    return path;
}

4. Bellman-Ford Algorithm

The Bellman-Ford algorithm is another dynamic routing algorithm used for finding the shortest path in a graph. It handles both positive and negative edge weights but can be slower than Dijkstra’s algorithm for graphs without negative cycles. Bellman-Ford algorithm is often used when considering time-dependent travel times or road closures, making it suitable for dynamic routing in transportation networks.

// Example code for Bellman-Ford Algorithm
#include <iostream>
#include <vector>

struct Edge {
    int source;
    int destination;
    int weight;
};

std::vector<int> BellmanFord(std::vector<Edge>& edges, int vertices, int source) {
    std::vector<int> distances(vertices, INT_MAX);
    
    distances[source] = 0;
    
    for (int i = 0; i < vertices - 1; ++i) {
        for (const Edge& edge : edges) {
            if (distances[edge.source] != INT_MAX && distances[edge.source] + edge.weight < distances[edge.destination]) {
                distances[edge.destination] = distances[edge.source] + edge.weight;
            }
        }
    }
    
    return distances;
}

5. Conclusion

Dynamic routing algorithms are vital for optimizing transportation networks by considering real-time factors. In this blog post, we explored three popular dynamic routing algorithms - Dijkstra’s algorithm, A* algorithm, and Bellman-Ford algorithm - and provided example code implementations in C++. These algorithms form the foundation for efficient path planning in transportation systems, enabling us to reach our destinations promptly and safely.

6. Resources

For further reading and more in-depth knowledge, you can refer to the following resources:

#techblog #routing #C++

Table of Contents