gpt-3.5-turbo-0301· OpenAI
WildChat-4.8M (AI2)
реализуй функцию на C++ реализующую алгоритм дейкстеры для поиска самого надежного пути…
- User
реализуй функцию на C++ реализующую алгоритм дейкстеры для поиска самого надежного пути в графах заданных матрицей смежности
- Assistant
#include<iostream> #include<climits> // для INT_MAX #define V 5 // количество вершин using namespace std; int minDistance(int dist[], bool sptSet[]) // функция для поиска вершины с минимальным расстоянием из множества непросмотренных вершин { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } void printSolution(int dist[]) // функция для вывода расстояния от начальной вершины до всех вершин графа { cout << "Vertex \t\t Distance from Source" << endl; for (int i = 0; i < V; i++) cout << i << "\t\t" << dist[i] << endl; } void dijkstra(int graph[V][V], int src) // функция для поиска самого надежного пути { int dist[V]; bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; // обновление расстояния к вершине v, если найден более короткий путь через u } printSolution(dist); } int main() { int graph[V][V] = { { 0, 10, 20, 0, 0 }, { 10, 0, 5, 30, 0 }, { 20, 5, 0, 0, 100 }, { 0, 30, 0, 0, 10 }, { 0, 0, 100, 10, 0 } }; dijkstra(graph, 0); // вызов функции для поиска самого надежного пути начиная с вершины 0 return 0; }``` Здесь приведен пример реализации алгоритма Дейкстры для графа на 5 вершинах с заданной матрицей смежности. - User
используй в предыдущей программе stdio.h
- Assistant
Конечно, вот код с использованием
stdio.hдля ввода матрицы смежности и вывода результата:#include<stdio.h> #include<limits.h> // для INT_MAX #define V 5 // количество вершин void printSolution(int dist[]) // функция для вывода расстояния от начальной вершины до всех вершин графа { printf("Vertex \t\t Distance from Source\n"); for (int i = 0; i < V; i++) printf("%d \t\t %d\n", i, dist[i]); } int minDistance(int dist[], bool sptSet[]) // функция для поиска вершины с минимальным расстоянием из множества непросмотренных вершин { int min = INT_MAX, min_index; for (int v = 0; v < V; v++) if (sptSet[v] == false && dist[v] <= min) min = dist[v], min_index = v; return min_index; } void dijkstra(int graph[V][V], int src) // функция для поиска самого надежного пути { int dist[V]; bool sptSet[V]; for (int i = 0; i < V; i++) dist[i] = INT_MAX, sptSet[i] = false; dist[src] = 0; for (int count = 0; count < V - 1; count++) { int u = minDistance(dist, sptSet); sptSet[u] = true; for (int v = 0; v < V; v++) if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX && dist[u] + graph[u][v] < dist[v]) dist[v] = dist[u] + graph[u][v]; // обновление расстояния к вершине v, если найден более короткий путь через u } printSolution(dist); } int main() { int graph[V][V]; printf("Enter the adjacency matrix:\n"); for (int i = 0; i < V; i++) for (int j = 0; j < V; j++) scanf("%d", &graph[i][j]); int src = 0; printf("Enter the source vertex: "); scanf("%d", &src); dijkstra(graph, src); // вызов функции для поиска самого надежного пути начиная с заданной вершины return 0; }Здесь производится ввод матрицы смежности с помощью
scanf()и вывод результата с помощьюprintf().
Other models, same or similar prompt
Responses were produced in different, uncontrolled contexts (system prompts, settings, prior turns). This is not a benchmark.