|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
#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:
INFis defined as a large value to represent infinity, indicating no direct path between vertices.graphis a 2D vector wheregraph[i][j]represents the weight of the edge from vertexito vertexj.
- Floyd-Warshall Algorithm (
floydWarshall):- Initializes a distance matrix
distwith 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 vertexk. - If a shorter path is found through vertex
k, it updates the distancedist[i][j].
- Iterates over each pair of vertices
- After computing shortest paths, prints the distance matrix where each entry
dist[i][j]shows the shortest path distance from vertexito vertexj. If no path exists, it showsINF.
- Initializes a distance matrix
- Main Function (
main):- Prompts the user to enter the number of vertices and the adjacency matrix of the graph.
- Calls
floydWarshallto 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.