Alg_Lab_10 (lll semester)

#include "stdafx.h"
#include <iostream>
#include <iomanip>
using namespace std;

void Dijkstra(int* GR[], int st, int V)
{
    int *distance = new int[V];
    int count, index, i, u, m = st + 1;
    bool *visited = new bool[V];
    for (i = 0; i<V; i++)
    {
        distance[i] = INT_MAX; visited[i] = false;
    }
    distance[st] = 0;
    for (count = 0; count<V - 1; count++)
    {
        int min = INT_MAX;
        for (i = 0; i<V; i++)
            if (!visited[i] && distance[i] <= min)
            {
                min = distance[i]; index = i;
            }
        u = index;
        visited[u] = true;
        for (i = 0; i<V; i++)
            if (!visited[i] && GR[u][i] && distance[u] != INT_MAX &&
                distance[u] + GR[u][i]<distance[i])
                distance[i] = distance[u] + GR[u][i];
    }
    cout << "Стоимость пути из начальной вершины до остальных:\t\n";
    for (i = 0; i<V; i++) if (distance[i] != INT_MAX)
        cout << m << " > " << i + 1 << " = " << distance[i] << endl;
    else cout << m << " > " << i + 1 << " = " << "маршрут недоступен" << endl;
}

void Floyd(int* D[], int V)
{
    int k;
    for (int i = 0; i<V; i++)
        D[i][i] = 0;
    for (int k = 0; k<V; k++)
        for (int i = 0; i<V; i++)
            for (int j = 0; j<V; j++)
                if (D[i][k] && D[k][j] && i != j)
                    if (D[i][k] + D[k][j]<D[i][j] || D[i][j] == 0)
                        D[i][j] = D[i][k] + D[k][j];


    cout << setw(4);
    for (int i = 0; i < V; i++)
        cout << "|x" << i + 1;
    cout << endl;
    for (int i = 0; i < V; i++)
    {
        cout << "X" << i + 1 << '|';
        for (int j = 0; j < V; j++)
            cout << D[i][j] << "  ";
        cout << endl;
    }
}
int main()
{
    setlocale(LC_ALL, "Rus");
    int V;
    cout << "Введите размерность графа: ";
    while (!(cin >> V) || (cin.peek() != '\n' || !(V >= 2)))
    {
        cin.clear();
        while (cin.get() != '\n');
        cout << "Введено недопустимое значение " << V << " Повторите попытку." << endl;
    }
    int **VES = new int*[V];
    for (int i = 0; i < V; i++)
        VES[i] = new int[V];
    int VV = V*V;
    int start = 0;;
    cout << "Заполните матрицу весов графа " << endl;
    cout << setw(4);
    for (int i = 0; i < V; i++)
        cout << "|x" << i + 1;
    cout << endl;
    for (int i = 0; i < V; i++)
    {
        cout << "X" << i + 1 << '|';
        for (int j = 0; j < V; j++)
            cin >> VES[i][j];
    }
    cout << "Начальная вершина >> ";
    cin >> start;
    cout << "Алгоритм Дейкстры" << endl;
    Dijkstra(VES, start - 1, V);
    cout << "Алгоритм Флойда" << endl;
    Floyd(VES, V);
    system("pause");
}