напиши функцию на C++ которая бы принимала на вход начальное и конечное значение…
- User
напиши функцию на C++ которая бы принимала на вход начальное и конечное значение ориентированного графа заданного через матрицу смежности, включающую надежность графа и считала бы кратчайший путь между заданными вершинами
- Assistant
Для решения этой задачи можно использовать алгоритм Дейкстры. Вот пример функции на C++:
#include <iostream> #include <vector> #include <queue> #include <climits> using namespace std; // Функция для поиска кратчайшего пути между вершинами // start и end в ориентированном графе с матрицей смежности matrix // и надежностью reliability void findShortestPath(int start, int end, vector<vector<int>> matrix, vector<vector<float>> reliability) { int n = matrix.size(); // количество вершин в графе vector<float> dist(n, INT_MAX); // массив расстояний от стартовой вершины до остальных vector<int> prev(n, -1); // массив предшествующих вершин на кратчайшем пути dist[start] = 0; // расстояние от стартовой вершины до нее самой равно 0 priority_queue<pair<float, int>, vector<pair<float, int>>, greater<pair<float, int>>> pq; pq.push(make_pair(0, start)); // добавляем стартовую вершину в очередь с приоритетом while (!pq.empty()) { int u = pq.top().second; pq.pop(); for (int v = 0; v < n; v++) { if (matrix[u][v] == 1) { // проверяем, есть ли ребро между вершинами u и v float weight = (-1) * log(reliability[u][v]); // считаем вес ребра по формуле из задания float alt = dist[u] + weight; if (alt < dist[v]) { // если новый путь короче старого, обновляем расстояние и предшествующую вершину dist[v] = alt; prev[v] = u; pq.push(make_pair(dist[v], v)); } } } } // восстанавливаем путь, начиная с конечной вершины vector<int> path; int u = end; while (prev[u] != -1) { path.push_back(u); u = prev[u]; } path.push_back(u); reverse(path.begin(), path.end()); // выводим путь и его длину cout << "Shortest path from " << start << " to " << end << ": "; for (int i = 0; i < path.size(); i++) { if (i != 0) cout << " -> "; cout << path[i]; } cout << ", length = " << exp((-1) * dist[end]) << endl; // выводим длину пути в исходном формате } int main() { // пример использования функции vector<vector<int>> matrix = {{0, 1, 0, 1}, {0, 0, 0, 1}, {1, 0, 0, 0}, {0, 0, 1, 0}}; vector<vector<float>> reliability = {{1, 0.8, 0, 0.9}, {0, 1, 0, 0.7}, {1, 0, 1, 0}, {0, 0, 0.6, 1}}; findShortestPath(0, 3, matrix, reliability); return 0; }В этом примере мы задаем матрицу смежности и надежность графа в виде двумерных векторов. Функция
findShortestPathпринимает три аргумента: начальную и конечную вершины, а также матрицу смежности и надежность графа. Внутри функции мы сначала инициализируем массивы расстояний и предшествующих вершин, затем запускаем алгоритм Дейкстры, обновляя эти массивы по мере его работы. После того, как мы найдем кратчайший путь, восстанавливаем его по массиву предшествующих вершин и выводим в консоль. Обратите внимание, что мы используем логарифмическую шкалу для вычисления веса ребер, а затем переводим длину пути в исходный формат с помощью экспоненты.
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.