Нужно найти максимальный простой путь в графе - 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;
}
Объяснение кода листинга программы
В этом коде реализуется алгоритм Дейкстры для поиска кратчайшего пути во взвешенном графе. Вот список действий, которые происходят в коде:
- Ввод количества вершин графа.
- Инициализация матрицы A, которая представляет собой взвешенный граф. Значение 0 означает, что между вершинами i и j есть бесконечное количество путей, а другие значения представляют собой вес ребра между этими вершинами.
- Инициализация переменных tec и short1. Переменная tec содержит текущую минимальную длину пути от начальной вершины до каждой другой вершины, а переменная short1 содержит предыдущую вершину в кратчайшем пути от начальной вершины до текущей вершины.
- Цикл по всем вершинам графа.
- Внутри цикла поиск новой кратчайшей длины пути от начальной вершины до текущей вершины. Если текущая длина пути короче, чем текущая минимальная длина пути плюс вес ребра между текущей вершиной и следующей вершиной в пути, то обновление текущей минимальной длины пути и обновление предыдущей вершины в пути.
- Обновление текущей минимальной длины пути и предыдущей вершины в пути.
- Цикл по всем вершинам графа.
- Вывод кратчайших длин путей от начальной вершины до каждой другой вершины. Этот код решает задачу поиска максимального простого пути в графе, а не задачу поиска кратчайшего пути. Код, который решает задачу поиска максимального простого пути, будет немного отличаться.