Skip to content
TheChatArchiveThe Chat Archive
gpt-3.5-turbo-0301· OpenAIAi2 WildChat-4.8M (AI2)

Реализуй на C++ программу, которая бы вычисляла самый надежный путь в графе между…

  1. User

    Реализуй на C++ программу, которая бы вычисляла самый надежный путь в графе между заданными вершинами. Не используй и

  2. Assistant

    Код программы:

    #include <iostream>
    #include <cstring>
    
    using namespace std;
    
    const int N = 100;
    
    int n; // количество вершин в графе
    int g[N][N]; // матрица смежности графа
    int d[N]; // массив расстояний от стартовой вершины до остальных вершин
    bool used[N]; // массив пометок о посещении вершин
    
    int dijkstra(int start, int finish) {
        memset(d, -1, sizeof(d)); // инициализируем массив расстояний
        memset(used, false, sizeof(used)); // инициализируем массив пометок
        d[start] = 0; // расстояние от стартовой вершины до нее самой равно 0
    
        for (int i = 0; i < n; i++) {
            int v = -1;
            // выбираем вершину с минимальным расстоянием, которую еще не посетили
            for (int j = 0; j < n; j++) {
                if (!used[j] && (v == -1 || d[j] < d[v])) {
                    v = j;
                }
            }
    
            // если не нашли такой вершины, значит, путь до остальных недостижим
            if (d[v] == -1) {
                break;
            }
    
            used[v] = true; // помечаем вершину как посещенную
    
            // релаксируем все вершины, смежные с текущей
            for (int j = 0; j < n; j++) {
                if (g[v][j] != -1 && (d[j] == -1 || d[j] > d[v] + g[v][j])) {
                    d[j] = d[v] + g[v][j];
                }
            }
        }
    
        return d[finish]; // возвращаем расстояние до финишной вершины
    }
    
    int main() {
        // вводим данные о графе
        cin >> n;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> g[i][j];
            }
        }
    
        // вводим начальную и конечную вершину
        int start, finish;
        cin >> start >> finish;
    
        // выводим расстояние между начальной и конечной вершинами
        cout << dijkstra(start, finish) << endl;
    
        return 0;
    }
    
  3. User

    используй <stdio.h> для ввода и вывода данных

  4. Assistant

    Код программы, использующей <stdio.h> для ввода и вывода данных:

    #include <stdio.h>
    #include <string.h>
    
    #define N 100
    
    int n; // количество вершин в графе
    int g[N][N]; // матрица смежности графа
    int d[N]; // массив расстояний от стартовой вершины до остальных вершин
    int used[N]; // массив пометок о посещении вершин
    
    int dijkstra(int start, int finish) {
        memset(d, -1, sizeof(d)); // инициализируем массив расстояний
        memset(used, 0, sizeof(used)); // инициализируем массив пометок
        d[start] = 0; // расстояние от стартовой вершины до нее самой равно 0
    
        for (int i = 0; i < n; i++) {
            int v = -1;
            // выбираем вершину с минимальным расстоянием, которую еще не посетили
            for (int j = 0; j < n; j++) {
                if (!used[j] && (v == -1 || d[j] < d[v])) {
                    v = j;
                }
            }
    
            // если не нашли такой вершины, значит, путь до остальных недостижим
            if (d[v] == -1) {
                break;
            }
    
            used[v] = 1; // помечаем вершину как посещенную
    
            // релаксируем все вершины, смежные с текущей
            for (int j = 0; j < n; j++) {
                if (g[v][j] != -1 && (d[j] == -1 || d[j] > d[v] + g[v][j])) {
                    d[j] = d[v] + g[v][j];
                }
            }
        }
    
        return d[finish]; // возвращаем расстояние до финишной вершины
    }
    
    int main() {
        // вводим данные о графе
        scanf("%d", &n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
            }
        }
    
        // вводим начальную и конечную вершину
        int start, finish;
        scanf("%d %d", &start, &finish);
    
        // выводим расстояние между начальной и конечной вершинами
        printf("%d\n", dijkstra(start, finish));
    
        return 0;
    }
    
  5. User

    добавь выводы с пояснениями о том, что нужно вводить в данный момент

  6. Assistant

    Код программы с комментариями и выводами:

    #include <stdio.h>
    #include <string.h>
    
    #define N 100
    
    int n; // количество вершин в графе
    int g[N][N]; // матрица смежности графа
    int d[N]; // массив расстояний от стартовой вершины до остальных вершин
    int used[N]; // массив пометок о посещении вершин
    
    int dijkstra(int start, int finish) {
        memset(d, -1, sizeof(d)); // инициализируем массив расстояний
        memset(used, 0, sizeof(used)); // инициализируем массив пометок
        d[start] = 0; // расстояние от стартовой вершины до нее самой равно 0
    
        for (int i = 0; i < n; i++) {
            int v = -1;
            // выбираем вершину с минимальным расстоянием, которую еще не посетили
            for (int j = 0; j < n; j++) {
                if (!used[j] && (v == -1 || d[j] < d[v])) {
                    v = j;
                }
            }
    
            // если не нашли такой вершины, значит, путь до остальных недостижим
            if (d[v] == -1) {
                break;
            }
    
            used[v] = 1; // помечаем вершину как посещенную
    
            // релаксируем все вершины, смежные с текущей
            for (int j = 0; j < n; j++) {
                if (g[v][j] != -1 && (d[j] == -1 || d[j] > d[v] + g[v][j])) {
                    d[j] = d[v] + g[v][j];
                }
            }
        }
    
        return d[finish]; // возвращаем расстояние до финишной вершины
    }
    
    int main() {
        // вводим количество вершин графа
        printf("Введите количество вершин графа: ");
        scanf("%d", &n);
    
        // вводим матрицу смежности графа
        printf("Введите матрицу смежности графа:\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%d", &g[i][j]);
            }
        }
    
        // вводим начальную и конечную вершину
        int start, finish;
        printf("Введите стартовую и финишную вершины: ");
        scanf("%d %d", &start, &finish);
    
        // выводим расстояние между начальной и конечной вершинами
        int distance = dijkstra(start, finish);
        if (distance == -1) {
            printf("Путь не найден!\n");
        } else {
            printf("Расстояние между вершинами %d и %d равно %d\n", start, finish, distance);
        }
    
        return 0;
    }
    

    В данной программе для начала требуется ввести количество вершин графа. Затем необходимо ввести матрицу смежности графа (для этого необходимо вводить элементы матрицы через пробелы или переходы на новую строку). После этого нужно ввести номера стартовой и финишной вершин. Программа выводит расстояние между указанными вершинами, либо сообщение об отсутствии пути.

  7. User

    переделай программу так, что бы надежность ребра выражалась в вещественных числах

  8. Assistant

    Код программы, в которой надежность ребер выражается в вещественных числах:

    #include <stdio.h>
    #include <string.h>
    #include <limits.h>
    
    #define N 100
    
    int n;                 // количество вершин в графе
    double g[N][N];        // матрица смежности графа
    double d[N];           // массив расстояний от стартовой вершины до остальных вершин
    int used[N];           // массив пометок о посещении вершин
    
    double dijkstra(int start, int finish) {
        memset(d, 0, sizeof(d));  // инициализируем массив расстояний
        memset(used, 0, sizeof(used));  // инициализируем массив пометок
    
        d[start] = 1;  // надежность от стартовой вершины до нее самой равно 1
    
        for (int i = 0; i < n; i++) {
            int v = -1;
            // выбираем вершину с максимальной надежностью, которую еще не посетили
            for (int j = 0; j < n; j++) {
                if (!used[j] && (v == -1 || d[j] > d[v])) {
                    v = j;
                }
            }
    
            // если не нашли такой вершины, значит, путь до остальных недостижим
            if (v == -1 || d[v] == 0) {
                return 0;
            }
    
            used[v] = 1;  // помечаем вершину как посещенную
    
            // релаксируем все вершины, смежные с текущей
            for (int j = 0; j < n; j++) {
                if (g[v][j] > 0 && (!used[j] || d[j] < d[v] * g[v][j])) {
                    d[j] = d[v] * g[v][j];
                }
            }
        }
    
        return d[finish];  // возвращаем надежность пути
    }
    
    int main() {
        // вводим количество вершин графа
        printf("Введите количество вершин графа: ");
        scanf("%d", &n);
    
        // вводим матрицу смежности графа
        printf("Введите матрицу смежности графа:\n");
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                scanf("%lf", &g[i][j]);
            }
        }
    
        // вводим начальную и конечную вершину
        int start, finish;
        printf("Введите стартовую и финишную вершины: ");
        scanf("%d %d", &start, &finish);
    
        // выводим надежность пути между начальной и конечной вершинами
        double reliability = dijkstra(start, finish);
        if (reliability == 0) {
            printf("Путь не найден!\n");
        } else {
            printf("Надежность пути между вершинами %d и %d равна %lf\n", start, finish, reliability);
        }
    
        return 0;
    }
    

    В данной программе для начала требуется ввести количество вершин графа. Затем необходимо ввести матрицу смежности графа (для этого необходимо вводить элементы матрицы через пробелы или переходы на новую строку). После этого нужно ввести номера стартовой и финишной вершин. Программа выводит надежность пути между указанными вершинами, либо сообщение об отсутствии пути.

  9. User

    обьясни что представляет собой матрица смежности которую нужно вводить в данную программу

  10. Assistant

    Матрица смежности - это способ представления неориентированного графа в виде квадратной матрицы. Граф представляется в виде таблицы, в которой строки и столбцы соответствуют вершинам графа, а на пересечении i-ой строки и j-ого столбца находится число, указывающее на наличие/отсутствие ребра между i-ой и j-ой вершинами. Если ребро есть, то в матрице стоит единица или вес ребра, если граф взвешенный. Если ребра нет, то в матрице стоит ноль.

    Для неориентированного графа матрица смежности является симметричной относительно главной диагонали.

    Пример матрицы смежности графа:

    0 1 1 0
    1 0 1 1
    1 1 0 0
    0 1 0 0
    

    Данный граф состоит из 4 вершин. Здесь имеется ребро между вершинами 1 и 2, между вершинами 1 и 3, между вершинами 2 и 3, а также между вершинами 2 и 4. Ребра между вершинами 3 и 4 нет. В такой матрице для более легкого чтения можно разделить числа пробелами или переносами строк.

  11. User

    переделай программу так, что бы она работала с ориентированными графами

  12. Assistant

    Код программы, работающей с ориентированными графами:

    #include <stdio.h>
    #include <string.h>
    #include <limits.h>
    
    #define N 100
    
    int n;                 // количество вершин в графе
    double g[N][N];        // матрица смежности графа
    double d[N];           // массив расстояний от стартовой вершины до остальных вершин
    int used[N];           // массив пометок о посещении вершин
    
    double dijkstra(int start, int finish) {
        memset(d, 0, sizeof(d));  // инициализируем массив расстояний
        memset(used, 0, sizeof(used));  // инициализируем массив пометок
    
        d[start] = 1;  // надежность от стартовой вершины до нее самой равно 1
    
        for (int i = 0; i < n; i++) {
            int v = -1;
            // выбираем вершину с максимальной надежностью, которую еще не посетили
            for (int j =