Нужно найти максимальный простой путь в графе - C (СИ)

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

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

Здравствуйте Есть такая задача: "Нужно найти максимальный простой путь в графе" Как я понял, тут нужно использовать какой-либо модифицированный алгоритм. Можно ли взять Флойда-Уоршала, который ищет кратчайшие расстояния и переделать в максимальные?

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

textual
Листинг программы
#include <stdio.h>
#include <math.h>
 
int main() {
    int A[100][100];
    int B,i,j,n,Nmin,max,minpath;
    int L[100][100];
    int tec[100];
    int short1[100];
    printf("Введите количество вершин");
    scanf("%d",&n);
    max=100;
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        {
            A[i][j]=0;
        }
        tec[i]=max;
        short1[i]=max;
        
    }
    i=0;
    j=0;
    short1[1]=0;
    Nmin=1;
    minpath=0;
    for(i=1;i<=n;i++);
    {
        for(j=1;j<=n;j++);
        {
            if (short1[j]==max)
            {
                if (tec[j]>minpath+A[Nmin][j]);
                {
                    tec[j]=minpath+A[Nmin][j];
                }
            }
        }
        minpath=max;
        for(j=2;j<=n;j++);
        {
            if(short1[j]==max);
            {
                if(tec[j=minpath]);
                {
                    minpath=tec[j];
                    Nmin=j;
                }
            }
        }
        short1[Nmin]=minpath;
        tec[Nmin]=max;
    }
    for(i=2;i<=n;i++)
    {
        printf("%d \n",short1[i]);
    }
    return 0;
}

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

В этом коде реализуется алгоритм Дейкстры для поиска кратчайшего пути во взвешенном графе. Вот список действий, которые происходят в коде:

  1. Ввод количества вершин графа.
  2. Инициализация матрицы A, которая представляет собой взвешенный граф. Значение 0 означает, что между вершинами i и j есть бесконечное количество путей, а другие значения представляют собой вес ребра между этими вершинами.
  3. Инициализация переменных tec и short1. Переменная tec содержит текущую минимальную длину пути от начальной вершины до каждой другой вершины, а переменная short1 содержит предыдущую вершину в кратчайшем пути от начальной вершины до текущей вершины.
  4. Цикл по всем вершинам графа.
  5. Внутри цикла поиск новой кратчайшей длины пути от начальной вершины до текущей вершины. Если текущая длина пути короче, чем текущая минимальная длина пути плюс вес ребра между текущей вершиной и следующей вершиной в пути, то обновление текущей минимальной длины пути и обновление предыдущей вершины в пути.
  6. Обновление текущей минимальной длины пути и предыдущей вершины в пути.
  7. Цикл по всем вершинам графа.
  8. Вывод кратчайших длин путей от начальной вершины до каждой другой вершины. Этот код решает задачу поиска максимального простого пути в графе, а не задачу поиска кратчайшего пути. Код, который решает задачу поиска максимального простого пути, будет немного отличаться.

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

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