Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //Пример входного файла "graph.txt":
- //Количество вершин
- //Исходная вершина
- //u v weight
- //u v weight
- //
- //где u - исходная вершина, v - конечная, weight - вес ребра
- #include <iostream>
- #include <fstream>
- #include <vector>
- #include <limits>
- using namespace std;
- int INF = numeric_limits<int>::max(); // Значение "бесконечность"
- // Структура для представления ребра графа
- struct Edge
- {
- int destination; // Вершина, в которую ведет ребро
- int weight; // Вес ребра
- };
- void floyd_warshall_algorithm(vector<vector<Edge>>& graph, int number_of_vertices, vector<vector<int>>& distances)
- {
- // Элементы на диагонали матрицы расстояний равны 0
- for (int i = 0; i < number_of_vertices; i++)
- distances[i][i] = 0;
- // Заполнение матрицы расстояний из графа
- for (int u = 0; u < number_of_vertices; u++)
- for (Edge edge : graph[u])
- distances[u][edge.destination] = edge.weight;
- // Вычисление кратчайших путей между всеми парами вершин
- for (int k = 0; k < number_of_vertices; k++)
- for (int i = 0; i < number_of_vertices; i++)
- for (int j = 0; j < number_of_vertices; j++)
- // Если путь через вершину k короче текущего пути, обновляем его
- if (distances[i][k] != INF && distances[k][j] != INF && distances[i][k] + distances[k][j] < distances[i][j])
- distances[i][j] = distances[i][k] + distances[k][j];
- }
- // Обход графа в глубину
- void DFS(vector<vector<Edge>>& graph, int vertex, vector<bool>& visited)
- {
- visited[vertex] = true; // Помечаем текущую вершину как посещенную
- cout << vertex << " "; // Выводим текущую вершину
- // Рекурсивно обходим все соседние вершины
- for (Edge edge : graph[vertex])
- {
- int next_vertex = edge.destination;
- if (!visited[next_vertex])
- {
- DFS(graph, next_vertex, visited);
- }
- }
- }
- int main()
- {
- setlocale(LC_ALL, "rus");
- ifstream file("graph.txt");
- if (!file)
- {
- cout << "Не удалось открыть файл." << endl;
- return -1;
- }
- int number_of_vertices;
- file >> number_of_vertices; // Считываем количество вершин графа
- vector<vector<Edge>> graph(number_of_vertices); // Граф, представленный списком смежности
- int source; // Исходная вершина
- file >> source;
- // Считываем данные о ребрах графа из файла
- int u, v, weight;
- while (file >> u >> v >> weight)
- {
- graph[u].push_back({ v, weight });
- }
- file.close();
- // Инициализация матрицы расстояний
- vector<vector<int>> distances(number_of_vertices, vector<int>(number_of_vertices, INF));
- floyd_warshall_algorithm(graph, number_of_vertices, distances);
- // Вывод кратчайших путей
- cout << ' ' << '\t';
- for (int i = 0; i < number_of_vertices; i++)
- cout << i << '\t';
- cout << endl << endl;
- for (int i = 0; i < number_of_vertices; i++)
- {
- cout << i << '\t';
- for (int j = 0; j < number_of_vertices; j++)
- {
- if (distances[i][j] == INF)
- {
- cout << "нет пути" << '\t';
- }
- else
- {
- cout << distances[i][j] << '\t';
- }
- }
- cout << endl;
- }
- cout << endl;
- cout << "//////////////////////////////" << endl;
- cout << endl;
- cout << "Обход в глубину: ";
- vector<bool> visited(number_of_vertices, false);
- DFS(graph, source, visited);
- cout << endl;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement