Floyd-Warshall Algorithm Gaming Project in C++

Projects Inventory

3 months ago

#include <iostream>
#include <vector>
#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // Define a large value for infinity

// Function to perform Floyd-Warshall algorithm
void floydWarshall(vector<vector<int>>& graph) {
    int V = graph.size();

    // Initialize distance matrix
    vector<vector<int>> dist = graph;

    // Floyd-Warshall algorithm
    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][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
    }

    // Print the distance matrix
    cout << "Shortest distances between every pair of vertices:" << endl;
    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() {
    int V; // Number of vertices
    cout << "Enter the number of vertices: ";
    cin >> V;

    vector<vector<int>> graph(V, vector<int>(V, INF));

    cout << "Enter the adjacency matrix (use " << INF << " for infinity):" << endl;
    for (int i = 0; i < V; ++i) {
        for (int j = 0; j < V; ++j) {
            cin >> graph[i][j];
        }
    }

    floydWarshall(graph);

    return 0;
}

#include <iostream>

#include <vector>

#include <limits>

using namespace std;

const int INF = numeric_limits<int>::max(); // Define a large value for infinity

// Function to perform Floyd-Warshall algorithm

void floydWarshall(vector<vector<int>>& graph) {

int V = graph.size();

// Initialize distance matrix

vector<vector<int>> dist = graph;

// Floyd-Warshall algorithm

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][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

}

// Print the distance matrix

cout << "Shortest distances between every pair of vertices:" << endl;

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() {

int V; // Number of vertices

cout << "Enter the number of vertices: ";

cin >> V;

vector<vector<int>> graph(V, vector<int>(V, INF));

cout << "Enter the adjacency matrix (use " << INF << " for infinity):" << endl;

for (int i = 0; i < V; ++i) {

for (int j = 0; j < V; ++j) {

cin >> graph[i][j];

}

floydWarshall(graph);

return 0;

}

Explanation:

Constants and Data Structures:
- INF is defined as a large value to represent infinity, indicating no direct path between vertices.
- graph is a 2D vector where graph[i][j] represents the weight of the edge from vertex i to vertex j.
Floyd-Warshall Algorithm (floydWarshall):
- Initializes a distance matrix dist with the values from the input graph.
- Performs the Floyd-Warshall algorithm:
  - Iterates over each pair of vertices (i, j) and updates the shortest distance using an intermediate vertex k.
  - If a shorter path is found through vertex k, it updates the distance dist[i][j].
- After computing shortest paths, prints the distance matrix where each entry dist[i][j] shows the shortest path distance from vertex i to vertex j. If no path exists, it shows INF.
Main Function (main):
- Prompts the user to enter the number of vertices and the adjacency matrix of the graph.
- Calls floydWarshall to compute shortest paths and display the result.

Possible Enhancements:

Error Handling: Add validation for input data to ensure correct values for weights and matrix dimensions.

Support for Different Data Types: Modify the program to handle different types of weights (e.g., floats) or larger graphs.
Graph Representation: Allow input of the graph in different formats (e.g., edge list) and convert it to the adjacency matrix.
User Interface: Develop a graphical user interface (GUI) to facilitate graph input and visualization of results.

Explanation:

Possible Enhancements:

Related Posts: