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

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


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

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

7   голосов , оценка 3.571 из 5
Похожие ответы