Floyd Algorithm for All-Pairs Shortest Path

Implement Floyd's algorithm to compute shortest paths between all pairs of vertices in an undirected weighted graph. The graph is defined by vertices labeled from 1 to n and m edges with positive weights. For multiple queries, output the shotrest distance betwean two vertices or -1 if no path exists.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int vertices, edges;
    cin >> vertices >> edges;
    const int INF = 10005;
    vector<vector<int>> distance(vertices + 1, vector<int>(vertices + 1, INF));
    
    for (int i = 0; i < edges; ++i) {
        int u, v, w;
        cin >> u >> v >> w;
        distance[u][v] = w;
        distance[v][u] = w;
    }
    
    for (int i = 1; i <= vertices; ++i) {
        distance[i][i] = 0;
    }
    
    for (int k = 1; k <= vertices; ++k) {
        for (int i = 1; i <= vertices; ++i) {
            for (int j = 1; j <= vertices; ++j) {
                if (distance[i][k] < INF && distance[k][j] < INF) {
                    distance[i][j] = min(distance[i][j], distance[i][k] + distance[k][j]);
                }
            }
        }
    }
    
    int queries;
    cin >> queries;
    while (queries--) {
        int source, target;
        cin >> source >> target;
        if (distance[source][target] == INF) {
            cout << -1 << endl;
        } else {
            cout << distance[source][target] << endl;
        }
    }
    return 0;
}

BFS and A* Search for Knight's Minimum Moves

Calculate the minimum number of moves for a knight to travel between two positions on a 1000x1000 chessboard using BFS and A* search algorithms.

Breadth-First Search Implementation

BFS explores all possible knight moves level by level to find shortest path.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int board[1001][1001];
int directions[8][2] = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};

void bfs(int startX, int startY, int endX, int endY) {
    queue<pair<int, int>> q;
    q.push({startX, startY});
    board[startX][startY] = 0;
    
    while (!q.empty()) {
        auto [x, y] = q.front();
        q.pop();
        
        if (x == endX && y == endY) break;
        
        for (int i = 0; i < 8; ++i) {
            int nx = x + directions[i][0];
            int ny = y + directions[i][1];
            
            if (nx >= 1 && nx <= 1000 && ny >= 1 && ny <= 1000 && board[nx][ny] == 0) {
                board[nx][ny] = board[x][y] + 1;
                q.push({nx, ny});
            }
        }
    }
}

int main() {
    int testCases;
    cin >> testCases;
    while (testCases--) {
        int sx, sy, ex, ey;
        cin >> sx >> sy >> ex >> ey;
        memset(board, 0, sizeof(board));
        bfs(sx, sy, ex, ey);
        cout << board[ex][ey] << endl;
    }
    return 0;
}

A* Search Implementation

A* uses a heuristic function to prioritize nodes likely to lead to the goal, optimizing search efficiency.

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

int visited[1001][1001];
int moveSet[8][2] = {{-2, -1}, {-2, 1}, {-1, 2}, {1, 2}, {2, 1}, {2, -1}, {1, -2}, {-1, -2}};
int goalX, goalY;

struct Node {
    int x, y;
    int cost, heuristic, total;
    bool operator<(const Node& other) const {
        return total > other.total;
    }
};

int estimateDistance(const Node& node) {
    int dx = node.x - goalX;
    int dy = node.y - goalY;
    return dx * dx + dy * dy;
}

void aStarSearch(const Node& start) {
    priority_queue<Node> pq;
    pq.push(start);
    visited[start.x][start.y] = start.cost;
    
    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();
        
        if (current.x == goalX && current.y == goalY) break;
        
        for (int i = 0; i < 8; ++i) {
            Node neighbor;
            neighbor.x = current.x + moveSet[i][0];
            neighbor.y = current.y + moveSet[i][1];
            
            if (neighbor.x < 1 || neighbor.x > 1000 || neighbor.y < 1 || neighbor.y > 1000) continue;
            if (visited[neighbor.x][neighbor.y] != 0) continue;
            
            visited[neighbor.x][neighbor.y] = visited[current.x][current.y] + 1;
            neighbor.cost = current.cost + 5;
            neighbor.heuristic = estimateDistance(neighbor);
            neighbor.total = neighbor.cost + neighbor.heuristic;
            pq.push(neighbor);
        }
    }
}

int main() {
    int cases;
    cin >> cases;
    while (cases--) {
        int startX, startY;
        cin >> startX >> startY >> goalX >> goalY;
        memset(visited, 0, sizeof(visited));
        
        Node initial = {startX, startY, 0, 0, 0};
        initial.heuristic = estimateDistance(initial);
        initial.total = initial.cost + initial.heuristic;
        
        aStarSearch(initial);
        cout << visited[goalX][goalY] << endl;
    }
    return 0;
}