Last Updated:

Floyd-Worshell algorithm problem in C++

This algorithm is designed to find the shortest distances between all the vertices of a weighted directed graph.

A number of iterations are performed on the matrix. After the k-th iteration, matrix[i,j] contains the value of the shortest length of paths from vertex i to vertex j that do not pass through vertices with a number greater than k. Between the vertices of path i and j can be only those vertices whose numbers are less than or equal to k. In the k-th iteration, the following formula is used to calculate the matrix:


matrixk[i,j]=min(matrixk-1[i,j], matrixk-1[i,k] + matrixk-1[k,j])

Inputs: graph.txt

The first row is the number of vertices of the graph, followed by the edge directions of the oriented graph + the weight of the edge (the third column).

#include <iostream>
#include <fstream>
#include <algorithm>


void print_matrix(int** matrix, int numberOfVert, int INF) { //matrix - adjacency matrix
for (int i = 0; i < numberOfVert; i++) {
for (int j = 0; j < numberOfVert; j++) {
if (matrix[i][j] == INF) { //if cell is 101
std::cout << "INF" << " "; //print infinity symbol
}
else { //otherwise
std::cout << matrix[i][j] << " "; //display the value of the matrix cell
}
}
std::cout << std::endl; // do a line break after filling the row
}
}




void Floyd_Warshall(int **matrix, int numberOfVert) {
for (int k = 0; k < numberOfVert; k++) { //Iterate over all vertices and look for a shorter path through vertex k
for (int i = 0; i < numberOfVert; i++) {
for (int j = 0; j < numberOfVert; j++) {
matrix[i][j] = std::min(matrix[i][j], matrix[i][k] + matrix[k][j]); //The new edge value is the minimum between the old edge and the sum of the edges
}
}
}
}




int main() {
setlocale(LC_ALL, "English"); // connect Cyrillic


std::ifstream input_graph("graph.txt"); //open the file containing the graph data


intsize; //variable dimension of the matrix
input graph >> size; //fill in the dimension of the matrix


int **massive; //two-dimensional dynamic array for the matrix
massive = new int* [size]; //allocate memory for array cells with dimension size
for (int i = 0; i < size; i++) {
massive[i] = new int[size];
}


for (int i = 0; i < size; i++) { //set all cells to -1
for (int j = 0; j < size; j++) { //used as a flag for ease of calculation
massive[i][j] = -1;
}
}


int v1, v2, c; //variables for the value of the graph edges and their weight
while (!(input_graph.eof())) { //read the file before it ends
input_graph >> v1 >> v2 >> c; //assign appropriate values ​​to variables
massive[v1 - 1][v2 - 1] = c; //mirror fill the weight table
massive[v2 - 1][v1 - 1] = c; //mirror fill the weight table
}
input_graph.close(); //close the graph source data file


for (int i = 0; i < size; i++) { //run through the entire matrix
for (int j = 0; j < size; j++) {
if (i == j) { //if cell coordinates match
massive[i][j] = 0; //then assign 0 to the cell, 0 is the designation,
// which says that the vertex is directed towards itself
}
else { //otherwise
if (massive[i][j] == -1) { //if the cell is equal to the label (-1)
massive[i][j] = 101; //then assign 101 to the cell (there is no edge from the top)
}
}
}
}


std::ofstream matrix_size("matrix_from_size.txt"); //open the file with the weight matrix for writing
matrix_size << size << '\n'; //set the number of graph vertices in the first line
for (int i = 0; i < size; i++) {
for (int j = 0; j < size; j++) {
matrix_size << massive[i][j] << ' '; //fill the file with weights and
//indent each value
}
matrix_size << '\n'; //make a transition to a new line after filling the row
}
matrix_size.close(); // close the file


std::ifstream file("matrix_from_size.txt"); //open the file with the weight table for reading
int number_of_vert; //variable for matrix dimension
file >> number_of_vert; // extract the top from the file with dimension


// Adjacency matrix with graph edge weights (101 - no edge, 0 edge into itself)
int **matrix; //create a two-dimensional dynamic array for the matrix
matrix = new int*[number_of_vert]; //allocate memory
for (int i = 0; i < number_of_vert; i++) {
matrix[i] = new int[number_of_vert];
}


for (int i = 0; i < number_of_vert; i++) { //Read the edge weight matrix from the file
for (int j = 0; j < number_of_vert; j++) {
file >> matrix[i][j]; //to our matrix
}
}
file.close(); // close the file


Floyd_Warshall(matrix, number_of_vert); //call the calculation function, pass our matrix and the dimension of the matrix to it


std::ofstream result_matrix("result_matrix.txt"); //open the file with the result of calculations for writing
for (int i = 0; i < number_of_vert; i++) {
for (int j = 0; j < number_of_vert; j++) {
result_matrix << matrix[i][j] << ' '; //put the values ​​from our matrix into the file and indent
}
result_matrix << '\n'; //indent down after filling the row
}
result_matrix.close(); // close the file with the result


system("pause"); //wait for a keypress
return 0;
}

In such a simple way, we got acquainted with the topic "Floyd-Worshell algorithm"!