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

напиши функцию на C++ которая бы принимала на вход начальное и конечное значение…

  1. User

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

  2. 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 принимает три аргумента: начальную и конечную вершины, а также матрицу смежности и надежность графа. Внутри функции мы сначала инициализируем массивы расстояний и предшествующих вершин, затем запускаем алгоритм Дейкстры, обновляя эти массивы по мере его работы. После того, как мы найдем кратчайший путь, восстанавливаем его по массиву предшествующих вершин и выводим в консоль. Обратите внимание, что мы используем логарифмическую шкалу для вычисления веса ребер, а затем переводим длину пути в исходный формат с помощью экспоненты.

Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.