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