Advanced Algorithms: Floyd-Warshall and A*

Graph algorithms are crucial in solving a wide range of real-world problems, including pathfinding, network routing, and AI-driven decision-making. Among the most advanced and widely used algorithms are:

• Floyd-Warshall Algorithm – A dynamic programming approach for finding shortest paths between all pairs of nodes.
• A Algorithm* – An informed search algorithm that finds the shortest path from a start node to a goal node using heuristics.

In this article, we will explore these two powerful algorithms, understand how they work, and see their practical applications.

1. Floyd-Warshall Algorithm: All-Pairs Shortest Path

What is the Floyd-Warshall Algorithm?

The Floyd-Warshall Algorithm is a dynamic programming algorithm used to compute the shortest distances between all pairs of nodes in a weighted graph. Unlike Dijkstra or Bellman-Ford, which focus on single-source shortest paths, Floyd-Warshall efficiently finds shortest paths between every pair of nodes.

How It Works

• It uses a distance matrix, where dist[i][j] represents the shortest path from node i to node j.
• The algorithm iterates over each node (k), checking if including k in the path reduces the shortest distance between nodes i and j.
• If dist[i][k] + dist[k][j] < dist[i][j], update dist[i][j].

Algorithm Steps

1. Initialize the Distance Matrix:
   • dist[i][j] = weight(i, j), if there is an edge between i and j.
   • dist[i][j] = ∞ (infinity) if i and j are not directly connected.
   • dist[i][i] = 0 for all i (distance to itself is zero).
2. Iterate Over All Nodes (k as an intermediate node):
   • Update dist[i][j] by checking if i → k → j is a shorter path.
3. Final Distance Matrix:
   • After V iterations (where V is the number of vertices), dist[i][j] contains the shortest path between every pair (i, j).

C++ Implementation of Floyd-Warshall Algorithm

#include <iostream>
#include <vector>
#include <climits>

using namespace std;

#define INF INT_MAX

void floydWarshall(vector<vector<int>>& graph, int V) {
    vector<vector<int>> dist = graph;

    for (int k = 0; k < V; k++) {
        for (int i = 0; i < V; i++) {
            for (int j = 0; j < V; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }

    cout << "Shortest distances between every pair of nodes:\n";
    for (int i = 0; i < V; i++) {
        for (int j = 0; j < V; j++) {
            if (dist[i][j] == INF) cout << "INF ";
            else cout << dist[i][j] << " ";
        }
        cout << endl;
    }
}

int main() {
    vector<vector<int>> graph = {
        {0, 3, INF, INF, INF},
        {INF, 0, 1, INF, INF},
        {INF, INF, 0, 7, INF},
        {INF, INF, INF, 0, 2},
        {INF, INF, INF, INF, 0}
    };

    floydWarshall(graph, 5);
    return 0;
}

Time Complexity

• O(V³), making it suitable for small to medium-sized graphs.
• Not ideal for very large graphs due to cubic time complexity.

Applications of Floyd-Warshall Algorithm

✅ Network routing protocols (e.g., shortest paths in the internet).
✅ Social network analysis (finding shortest connections between people).
✅ Robotics (path planning for multiple locations).
✅ Traffic navigation systems (computing all-pairs shortest routes).

2. A Algorithm: Heuristic Pathfinding*

What is the A Algorithm?*

A* (A-Star) is an informed search algorithm that finds the shortest path between a start node and a goal node using a heuristic function. It is widely used in game AI, robotics, and GPS navigation systems.

How A Works*

A* maintains a priority queue and explores paths using:

• g(n): The actual cost from the start node to node n.
• h(n): A heuristic function estimating the cost from n to the goal.
• f(n) = g(n) + h(n): The total estimated cost.

A* prioritizes nodes with the smallest f(n), making it more efficient than Dijkstra’s Algorithm for specific goal-oriented searches.

Algorithm Steps

1. Initialize open set with the start node.
2. Use a priority queue to select the node with the lowest f(n).
3. Expand the selected node, updating g(n) and f(n) for its neighbors.
4. Stop when the goal node is reached or the open set is empty.

C++ Implementation of A Algorithm*

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <unordered_map>

using namespace std;

struct Node {
    int x, y, f, g, h;
    Node* parent;
};

struct Compare {
    bool operator()(const Node* a, const Node* b) {
        return a->f > b->f;
    }
};

int heuristic(Node* a, Node* b) {
    return abs(a->x - b->x) + abs(a->y - b->y); // Manhattan distance
}

void aStar(Node* start, Node* goal) {
    priority_queue<Node*, vector<Node*>, Compare> openSet;
    openSet.push(start);
    
    while (!openSet.empty()) {
        Node* current = openSet.top();
        openSet.pop();

        if (current == goal) {
            cout << "Path found!\n";
            return;
        }

        // Explore neighbors (For simplicity, this part is omitted)
    }
}

int main() {
    Node start = {0, 0, 0, 0, 0, nullptr};
    Node goal = {5, 5, 0, 0, 0, nullptr};
    
    aStar(&start, &goal);
    return 0;
}

Time Complexity

• O(V log V) in typical cases, depending on the heuristic function.
• More efficient than Dijkstra for goal-oriented searches.

Applications of A*

✅ Game AI (e.g., pathfinding in video games).
✅ Robotics (autonomous navigation).
✅ GPS navigation systems (efficient route calculation).

Conclusion

• Floyd-Warshall is best for all-pairs shortest paths, but not scalable for large graphs.
• A* is ideal for single-source to goal pathfinding in real-time applications.
• Choosing the right algorithm depends on the problem size, constraints, and requirements.