myuglycode

#include <iostream>
#include <iomanip>
#include <fstream>

#define INF INT_MAX

using namespace std;

void Floyd(int **graph, int verticesCount)
{
    for (int k = 0; k < verticesCount; k++)
    {
        for (int i = 0; i < verticesCount; i++)
        {
            for (int j = 0; j < verticesCount; j++)
            {
                if (graph[i][k] < INF && graph[k][j] < INF)
                    graph[i][j]= min(graph[i][j], graph[i][k] + graph[k][j]);
            }
        }
    }
}

int minimalPath(int from, int to, int **graph, int **tempGraph, int verticesCount)
{
    if (from == to) return 0;
    for (int i=0; i< verticesCount; i++)
        if (graph[from - 1][i] + tempGraph[i][to - 1] == graph[from - 1][to - 1])
        {
            if (from - 1 != i && to - 1 != i)
                return i+1;
        }
}
void inicializeGraph(ifstream input)
{
    input.open ("E:\\input.txt");
    int verticesCount;
    int from, to;
    input >> verticesCount;
    int ** graph = new int* [verticesCount];

    for (int i = 0; i < verticesCount; i++)
    {
        graph[i] = new int [verticesCount];
    }
    int ** tempGraph = new int* [verticesCount];

    for (int i = 0; i < verticesCount; i++)
    {
        tempGraph[i] = new int [verticesCount];
    }

    for (int i = 0; i < verticesCount; i++)
    {
        for (int j = 0; j < verticesCount; j++)
        {
            input >> graph[i][j];
            if (graph[i][j] == 9000000) graph[i][j] = INT_MAX;
            tempGraph[i][j] = graph[i][j];
        }
    }

    input >> from >> to;
    input.close();
}


void printGraph(int **graph, int verticesCount)
{
    for ( int i=0; i< verticesCount; i++)
    {
        for (int j=0; j< verticesCount; j++)
        {
            if (graph[i][j] == INF)
            {
                cout << "~" << " ";
            }
            else
            {
                cout << graph[i][j] << " ";
            }
        }
        cout << "\n";
    }
}
void main()
{
    setlocale(LC_ALL, "rus");
    ifstream input("E:\\input.txt");
    ofstream output;

    int verticesCount;
    int from, to;
    input >> verticesCount;
    int ** graph = new int* [verticesCount];

    for (int i = 0; i < verticesCount; i++)
    {
        graph[i] = new int [verticesCount];
    }
    int ** tempGraph = new int* [verticesCount];

    for (int i = 0; i < verticesCount; i++)
    {
        tempGraph[i] = new int [verticesCount];
    }

    for (int i = 0; i < verticesCount; i++)
    {
        for (int j = 0; j < verticesCount; j++)
        {
            input >> graph[i][j];
            if (graph[i][j] == 9000000) graph[i][j] = INT_MAX;
            tempGraph[i][j] = graph[i][j];
        }
    }

    input >> from >> to;
    input.close();
    cout << "Начальный граф "<< endl;
    printGraph(graph, verticesCount);

    Floyd(graph, verticesCount);

    cout << "Граф после применения алгоритма Флойда "<< endl;
    printGraph(graph, verticesCount);

    cout << "Кратчайший путь между двумя заданными вершинами"<< endl;
    cout << from <<" " << minimalPath(from, to, graph, tempGraph, verticesCount) <<" "<< to;

    output.open("E:\\output.txt");
    for (int i = 0; i < verticesCount; i++)
    {
        for (int j = 0; j < verticesCount; j++)
        {
            if (graph[i][j] == INF)
            {
                output << "~" << " ";
            }
            else
            {
                output << graph[i][j] << " ";
            }
        }
        output << endl;
    }
    output << "Кратчайший путь между двумя заданными вершинами"<< endl;
    output << from <<" " << minimalPath(from, to, graph, tempGraph, verticesCount) <<" "<< to << endl;

    output.close();
    system("pause");
}