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

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

  1. User

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

  2. 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; }

  3. User

    Не используй в решении

  4. 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 в противном случае.

  5. User

    добавь возможность задавать надежность каждому ребру

  6. 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 и записываем ее в соответствующую ячейку матрицы.

  7. User

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

  8. 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 и выводим полученный путь и надежность. Если пути между начальной и конечной вершинами не существует, выводим сообщение об ошибке.