Определение наименьшего пути между двумя заданными вершинами графа - C (СИ)

Узнай цену своей работы

Формулировка задачи:

Помогите пожалуйста. Нужна самая простая программа. Разработать алгоритм определения наименьшего пути между двумя заданными вершинами графа

Решение задачи: «Определение наименьшего пути между двумя заданными вершинами графа»

textual
Листинг программы
  1. //#include <iostream>
  2. #include <stdio.h>
  3. #include <limits.h>
  4. #include <locale.h>
  5. #define V 4
  6. //using namespace std;
  7. //алгоритм Дейкстры
  8. void Dijkstra(int GR[V][V], int st,int kon)
  9. {
  10.     int distance[V], count, index, i, u, m = st + 1;
  11.     short visited[V];
  12.     for (i = 0; i<V; i++)
  13.     {
  14.         distance[i] = INT_MAX; visited[i] = 0;
  15.     }
  16.     distance[st] = 0;
  17.     for (count = 0; count<V - 1; count++)
  18.     {
  19.         int min = INT_MAX;
  20.         for (i = 0; i<V; i++)
  21.         if (visited[i] == 0 && distance[i] <= min)
  22.         {
  23.             min = distance[i]; index = i;
  24.         }
  25.         u = index;
  26.         visited[u] = 1;
  27.         for (i = 0; i<V; i++)
  28.         if (visited[i] == 0 && GR[u][i] && distance[u] != INT_MAX &&
  29.             distance[u] + GR[u][i]<distance[i])
  30.             distance[i] = distance[u] + GR[u][i];
  31.     }
  32.     printf("Стоимость пути из начальной вершины до остальных:\t\n");
  33.     if (distance[kon - 1] != INT_MAX )
  34.         printf("%d > %d = %d \n", m,  kon, distance[kon-1]);
  35.     else printf("%d > %d = маршрут недоступен\n", m, kon);
  36. }
  37. //главная функция
  38. void main()
  39. {
  40.     setlocale(LC_ALL, "Rus");
  41.     int start, GR[V][V] = {
  42.         { 0, 5, 7, 9 },
  43.         { 5, 0, 10, 3 },
  44.         { 7, 10, 0, 1 },
  45.         { 9, 3, 1, 0 } };
  46.     int end;
  47.     printf("Начальная вершина >> "); scanf("%d", &start);
  48.     printf("Конечная вершина >> "); scanf("%d", &end);
  49.     Dijkstra(GR, start - 1, end);
  50. }

Объяснение кода листинга программы

  • Включаются необходимые заголовочные файлы — Определяется количество вершин графа (V) — Подключается библиотека для работы с локальцией — Определяется функция Dijkstra, которая реализует алгоритм Дейкстры — Внутри функции Dijkstra инициализируются массивы distance, visited, count, index, i, u, m = st + 1 — Задается начальная вершина (st) и конечная вершина (kon) — Выполняется цикл для нахождения кратчайшего пути от начальной вершины до всех остальных вершин графа — Если расстояние до текущей вершины (distance[i]) меньше текущего минимального расстояния, то обновляется текущее минимальное расстояние и индекс текущей вершины — Выполняется поиск кратчайшего пути от текущей вершины до всех остальных вершин графа — Выводится стоимость пути от начальной вершины до конечной вершины — Если путь от начальной вершины до конечной вершины недоступен, выводится сообщение об этом — В функции main задается начальная и конечная вершины — Вызывается функция Dijkstra для нахождения кратчайшего пути от начальной вершины до конечной вершины — Программа завершается

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

Оцени полезность:

7   голосов , оценка 3.571 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы