Алгоритм Флойда-Уоршела

#include <iostream>
#include <fstream>
#include <list>
using namespace std;
const int INF = 100500;
 
struct TEdge {
    int x, y, weight;
};//ребро
 
TEdge* ReadFromFile(char* filename,int &n,int &m)
{
    char s[10];
    FILE *f;
    f=fopen(filename,"rt");
    if (f==NULL)
    {
        cout<<"Incorrect filename"<<endl;
        system("pause");
        exit(0);
    }
    fgets(s,10,f);
    sscanf(s,"%d %d",&n,&m);
    TEdge* edges = new TEdge[m];
    for (int i = 0; i < m; i++)
    {
        fgets(s,10,f);
        sscanf(s,"%d %d %d",&(edges[i].x),&(edges[i].y),&(edges[i].weight));
    }
    return edges;
}
 
void PrintMatrix(int n,int** mat)
{
    for (int i=0;i<n;i++)
    {
        for (int j=0;j<n;j++)
            printf("%8d",mat[i][j]);
        printf("\n");
    }
}
 
int** Adjacency_Matrix(int n, int m, TEdge* edges)
{
    int** matrix_nn;
    matrix_nn = new int*[n];
    for (int i = 0; i < n; i++)
        matrix_nn[i]=new int[n];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            matrix_nn[i][j] = 0;
    for (int i = 0; i < m; i++)
        matrix_nn[edges[i].x - 1][edges[i].y - 1] += 1;
    return matrix_nn;
}
 
 
 
 
 
int** FloydWarshall(int n,int m,TEdge* e,int** prec,bool &negEdge)
{
    int** w = new int*[n];
    for (int i = 0; i < n; i++)
    {
        w[i]=new int[n];
        for (int j = 0; j < n; j++)
            w[i][j] = 0;
    }
    negEdge = false;
    for (int i = 0; i < m; i++)
    {
        w[e[i].x - 1][e[i].y - 1] = e[i].weight;
    }
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            if (w[i][j] == 0)
            {
                w[i][j] = INF;
                prec[i][j] = -1;
            }
            else prec[i][j] = i;
    for (int k = 0; k < n; k++)
    {
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++)
            {
                if (i == j) w[i][j] = 0;
                else
                    if (w[i][j] > w[i][k] + w[k][j])
                    {
                        w[i][j] = w[i][k] + w[k][j];
                        prec[i][j] = prec[k][j];
                    }
            }
    }
    return w;
}
 
 
 
void printPath(int* path,int i){
    if (path[i]==-1)
    {
        cout<<i<<" ";
        return;
    }
    printPath(path,path[i]);
    cout<<i<<" ";
}
 
 
 
int main()
{
    int n,
    m;
    TEdge* edges;
    //char arrow[5] = "->";
    int** AdjMat;
    char filename[255];
    cout<<"Enter input file name"<<endl;
    cin>>filename;
    edges = ReadFromFile(filename,n,m);
    AdjMat = Adjacency_Matrix(n,m,edges);
    cout<<"Adjacency Matrix :\n";
    PrintMatrix(n,AdjMat);
    int startVert = 0;
    cout<<"Enter start vert:\n";
    cin>>startVert;
    int endVert;
    cout<<"\nEnter end vert:\n";
    cin>>endVert;
    bool flag = false;
    int** prec = new int*[n];
    for (int i=0;i<n;i++)
        prec[i]= new int[n];
    int** dist = FloydWarshall(n,m,edges,prec,flag);
    if (flag) cout<<"Graph has negative edges\n";
    else
    {
        cout<<"Distance Matrix(Floyd Warshall) :\n";
        PrintMatrix(n,dist);
        cout<<endl;
        cout<<"Path from "<<startVert<<" to "<<endVert<<endl;
        if (dist[startVert][endVert]!=INF) printPath(prec[startVert],endVert);
        else cout<<"NO PATH\n";
        cout<<endl;
    }
        cout<<endl;
    system("pause");
}