напиши код на C++ который бы позволял вручную вводить ориентированный граф
- User
напиши код на C++ который бы позволял вручную вводить ориентированный граф
- Assistant
#include #include
using namespace std;
int main() { int n, m; cout << "Enter the number of vertices: "; cin >> n; cout << "Enter the number of edges: "; cin >> m; vector<vector> graph(n, vector()); cout << "Enter the directed edges (from vertex to vertex):\n"; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u].push_back(v); } return 0; }
- User
Не используй в решении
- Assistant
Хорошо, в таком случае можно использовать массивы и стандартную библиотеку для ввода-вывода:
#include <iostream> #include <cstring> using namespace std; const int MAXN = 100; // максимальное количество вершин в графе int graph[MAXN][MAXN]; // матрица смежности графа int n, m; // количество вершин и ребер int main() { memset(graph, 0, sizeof(graph)); // инициализируем матрицу нулями cout << "Enter the number of vertices: "; cin >> n; cout << "Enter the number of edges: "; cin >> m; cout << "Enter the directed edges (from vertex to vertex):\n"; for (int i = 0; i < m; i++) { int u, v; cin >> u >> v; graph[u][v] = 1; // добавляем ребро в граф } return 0; }Здесь матрица смежности графа представлена двумерным массивом
graph, элементgraph[i][j]равен 1, если существует ребро из вершиныiв вершинуj, и 0 в противном случае. - User
добавь возможность задавать надежность каждому ребру
- Assistant
Хорошо, для этого мы можем использовать двумерный массив
graph, гдеgraph[i][j]будет хранить надежность ребра из вершиныiв вершинуj. Вот код:#include <iostream> #include <cstring> using namespace std; const int MAXN = 100; // максимальное количество вершин в графе double graph[MAXN][MAXN]; // матрица смежности графа, хранящая надежность ребер int n, m; // количество вершин и ребер int main() { memset(graph, 0, sizeof(graph)); // инициализируем матрицу нулями cout << "Enter the number of vertices: "; cin >> n; cout << "Enter the number of edges: "; cin >> m; cout << "Enter the directed edges (from vertex to vertex) and their reliability:\n"; for (int i = 0; i < m; i++) { int u, v; double r; cin >> u >> v >> r; graph[u][v] = r; // добавляем ребро в граф } return 0; }Здесь при вводе ребра мы также вводим его надежность
rи записываем ее в соответствующую ячейку матрицы. - User
Напиши код на C++ который бы использовал данные, которые получает предыдущая программа и вычисляет самый надежный путь между заданными графами
- Assistant
Хорошо, для решения этой задачи мы можем использовать алгоритм Дейкстры для поиска кратчайшего пути в графе с заданными надежностями. Вот код:
#include <iostream> #include <cstring> #include <queue> using namespace std; const int MAXN = 100; // максимальное количество вершин в графе const double INF = 1e9; // "бесконечность" double graph[MAXN][MAXN]; // матрица смежности графа, хранящая надежность ребер double dist[MAXN]; // массив расстояний от начальной вершины до всех остальных int parent[MAXN]; // массив предков вершин int n, m, s, t; // количество вершин, ребер, начальная и конечная вершины void dijkstra(int s) { memset(dist, 0, sizeof(dist)); // инициализируем расстояния нулями memset(parent, -1, sizeof(parent)); // инициализируем предков -1 priority_queue<pair<double,int>> q; // очередь с приоритетом, хранящая пары (расстояние, вершина) q.push({1.0,s}); // добавляем стартовую вершину в очередь dist[s] = 1.0; // расстояние до самой себя равно 1.0 while (!q.empty()) { // пока очередь не пуста int u = q.top().second; // извлекаем вершину с наименьшим расстоянием q.pop(); for (int v = 0; v < n; v++) { // перебираем все соседние вершины if (graph[u][v] > 0) { // если есть ребро из u в v double w = graph[u][v]; // надежность ребра u -> v if (dist[u] * w > dist[v]) { // если нашли более надежный путь до v через u dist[v] = dist[u] * w; // обновляем расстояние до v parent[v] = u; // обновляем предка v q.push({dist[v],v}); // добавляем v в очередь } } } } } int main() { memset(graph, 0, sizeof(graph)); // инициализируем матрицу нулями cout << "Enter the number of vertices: "; cin >> n; cout << "Enter the number of edges: "; cin >> m; cout << "Enter the directed edges (from vertex to vertex) and their reliability:\n"; for (int i = 0; i < m; i++) { int u, v; double r; cin >> u >> v >> r; graph[u][v] = r; // добавляем ребро в граф } cout << "Enter the starting vertex: "; cin >> s; cout << "Enter the ending vertex: "; cin >> t; dijkstra(s); // запускаем алгоритм Дейкстры из начальной вершины if (dist[t] == 0) { // если расстояние до конечной вершины почти 0, то пути не существует cout << "No path found!\n"; } else { cout << "The most reliable path from " << s << " to " << t << " is:\n"; int cur = t; while (cur != -1) { // отображаем пройденный путь от конечной к начальной вершине cout << cur << " "; cur = parent[cur]; } cout << "\nWith reliability " << dist[t] << "\n"; } return 0; }Здесь мы используем функцию
dijkstraдля поиска кратчайшего пути из начальной вершины во все остальные с учетом надежности ребер. В функцииmainмы сначала вводим данные о графе и начальной/конечной вершинах, а затем запускаем функциюdijkstraи выводим полученный путь и надежность. Если пути между начальной и конечной вершинами не существует, выводим сообщение об ошибке.