Реализуй на C++ программу, которая бы вычисляла самый надежный путь в графе между…
- User
Реализуй на C++ программу, которая бы вычисляла самый надежный путь в графе между заданными вершинами. Не используй и
- 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; } - User
используй <stdio.h> для ввода и вывода данных
- 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; } - User
добавь выводы с пояснениями о том, что нужно вводить в данный момент
- 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; }В данной программе для начала требуется ввести количество вершин графа. Затем необходимо ввести матрицу смежности графа (для этого необходимо вводить элементы матрицы через пробелы или переходы на новую строку). После этого нужно ввести номера стартовой и финишной вершин. Программа выводит расстояние между указанными вершинами, либо сообщение об отсутствии пути.
- User
переделай программу так, что бы надежность ребра выражалась в вещественных числах
- 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; }В данной программе для начала требуется ввести количество вершин графа. Затем необходимо ввести матрицу смежности графа (для этого необходимо вводить элементы матрицы через пробелы или переходы на новую строку). После этого нужно ввести номера стартовой и финишной вершин. Программа выводит надежность пути между указанными вершинами, либо сообщение об отсутствии пути.
- User
обьясни что представляет собой матрица смежности которую нужно вводить в данную программу
- 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 нет. В такой матрице для более легкого чтения можно разделить числа пробелами или переносами строк.
- User
переделай программу так, что бы она работала с ориентированными графами
- 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 =