Определение наименьшего пути между двумя заданными вершинами графа - C (СИ)
Формулировка задачи:
Помогите пожалуйста. Нужна самая простая программа. Разработать алгоритм определения наименьшего пути между двумя заданными вершинами графа
Решение задачи: «Определение наименьшего пути между двумя заданными вершинами графа»
textual
Листинг программы
//#include <iostream> #include <stdio.h> #include <limits.h> #include <locale.h> #define V 4 //using namespace std; //алгоритм Дейкстры void Dijkstra(int GR[V][V], int st,int kon) { int distance[V], count, index, i, u, m = st + 1; short visited[V]; for (i = 0; i<V; i++) { distance[i] = INT_MAX; visited[i] = 0; } distance[st] = 0; for (count = 0; count<V - 1; count++) { int min = INT_MAX; for (i = 0; i<V; i++) if (visited[i] == 0 && distance[i] <= min) { min = distance[i]; index = i; } u = index; visited[u] = 1; for (i = 0; i<V; i++) if (visited[i] == 0 && GR[u][i] && distance[u] != INT_MAX && distance[u] + GR[u][i]<distance[i]) distance[i] = distance[u] + GR[u][i]; } printf("Стоимость пути из начальной вершины до остальных:\t\n"); if (distance[kon - 1] != INT_MAX ) printf("%d > %d = %d \n", m, kon, distance[kon-1]); else printf("%d > %d = маршрут недоступен\n", m, kon); } //главная функция void main() { setlocale(LC_ALL, "Rus"); int start, GR[V][V] = { { 0, 5, 7, 9 }, { 5, 0, 10, 3 }, { 7, 10, 0, 1 }, { 9, 3, 1, 0 } }; int end; printf("Начальная вершина >> "); scanf("%d", &start); printf("Конечная вершина >> "); scanf("%d", &end); Dijkstra(GR, start - 1, end); }
Объяснение кода листинга программы
- Включаются необходимые заголовочные файлы — Определяется количество вершин графа (V) — Подключается библиотека для работы с локальцией — Определяется функция Dijkstra, которая реализует алгоритм Дейкстры — Внутри функции Dijkstra инициализируются массивы distance, visited, count, index, i, u, m = st + 1 — Задается начальная вершина (st) и конечная вершина (kon) — Выполняется цикл для нахождения кратчайшего пути от начальной вершины до всех остальных вершин графа — Если расстояние до текущей вершины (distance[i]) меньше текущего минимального расстояния, то обновляется текущее минимальное расстояние и индекс текущей вершины — Выполняется поиск кратчайшего пути от текущей вершины до всех остальных вершин графа — Выводится стоимость пути от начальной вершины до конечной вершины — Если путь от начальной вершины до конечной вершины недоступен, выводится сообщение об этом — В функции main задается начальная и конечная вершины — Вызывается функция Dijkstra для нахождения кратчайшего пути от начальной вершины до конечной вершины — Программа завершается
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д