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