Форум на Исходниках.RU

Максимальный путь в графе

Infl1ght — Mon, 30 Jul 2018 14:52:33 +0000

Infl1ght:

Цитата Мавроди @ 28.11.07, 04:22

Алгоритм Дейкстры не подойдёт (

Алгоритм Дейкстры, действительно, не применим без дополнительных модификаций. Выложил очень простое решение с помощью метода динамического программирования:
https://gist.github.com/Infl1ght/54960c499e...cf1db9c6f11b8ec

Максимальный путь в графе

Мавроди — Wed, 28 Nov 2007 04:22:58 +0000

Мавроди: Алгоритм Дейкстры не подойдёт (

Максимальный путь в графе

_Spy_ — Sat, 24 Nov 2007 17:50:36 +0000

_Spy_: Хм...
Так возможно ли изменить вышенаписанный код так, чтобы максимальные пути искались, и искались правильно?

Или надо применять вообще какой-то другой алгоритм ?

Максимальный путь в графе

ArdI — Sat, 24 Nov 2007 17:40:06 +0000

ArdI: а, да, прошу прощения. ну это элементарно. Алгоритм дейстры работает правильно почему? Потому что соблюдается свойство подстуктуры. Т.е. если я на первом шаре выбираю минимальный путь из источника в какуюнить вершину, то я могу эту вершину после этого шага смело зачеркивать. Так вот дело в том, что для определенных максимальных путей это неверно, поэтому я не понимаю, что щас пытается мистер mo3r скаЗать.

Максимальный путь в графе

_Spy_ — Sat, 24 Nov 2007 17:37:15 +0000

_Spy_: Вообще-то Вы не дочитали мой пост до конца.
Я написАл, что этот код можно изменить для максимального пути, но у меня это не совсем получилось, и я подумал, что, возможно, кто-то поймёт, как это сделать.

Максимальный путь в графе

ArdI — Sat, 24 Nov 2007 17:35:07 +0000

ArdI: мистер Spy, ну вы совсем не в ту оперу, у нас тут речь идёт о Длинном пусти, а не о коротком.

Максимальный путь в графе

_Spy_ — Sat, 24 Nov 2007 17:26:18 +0000

_Spy_: Вот кусок кода поиска минимального пути в графе по алгоритму Дейкстры на С:
#include
#include
#include

#define TOPS 4

int main(int argc, char* argv[])
{

int infinity=10000;
int p = TOPS;
int** a = LoadDataFromFile("data1.txt");

int s = 1;
int g = 3;

int x[TOPS]; //Массив, содержащий единицы и нули для каждой вершины,
// x[i]=0 - еще не найден кратчайший путь в i-ю вершину,
// x[i]=1 - кратчайший путь в i-ю вершину уже найден
int t[TOPS]; //t[i] - длина кратчайшего пути от вершины s в i
int h[TOPS]; //h[i] - вершина, предшествующая i-й вершине
// на кратчайшем пути

// Инициализируем начальные значения массивов
int u; // Счетчик вершин
for (u=0;u {
t[u]=infinity; //Сначала все кратчайшие пути из s в i
//равны бесконечности
x[u]=0; // и нет кратчайшего пути ни для одной вершины
}
h[s]=0; // s - начало пути, поэтому этой вершине ничего не предшествует
t[s]=0; // Кратчайший путь из s в s равен 0
x[s]=1; // Для вершины s найден кратчайший путь
v=s; // Делаем s текущей вершиной

while(1)
{
// Перебираем все вершины, смежные v, и ищем для них кратчайший путь
for(u=0;u {
if(a[v][u]==0)continue; // Вершины u и v несмежные
if(x[u]==0 && t[u]>t[v]+a[v][u]) //Если для вершины u еще не
//найден кратчайший путь
// и новый путь в u короче чем
//старый, то
{
t[u]=t[v]+a[v][u]; //запоминаем более короткую длину пути в
//массив t и
h[u]=v; //запоминаем, что v->u часть кратчайшего
//пути из s->u
}
printf("%d\n",t[u]);
}

// Ищем из всех длин некратчайших путей самый короткий
int w=infinity; // Для поиска самого короткого пути
v=-1; // В конце поиска v - вершина, в которую будет
// найден новый кратчайший путь. Она станет
// текущей вершиной
for(u=0;u {
if(x[u]==0 && t[u] // путь и если длина пути в вершину u меньше
// уже найденной, то
{
v=u; // текущей вершиной становится u-я вершина
w=t[u];
}
}

if(v==-1)
{
printf("No ways");
break;
}
if(v==g) // Найден кратчайший путь,
{ // выводим его
printf("Min way = ");
u=g;
while(u!=s)
{
printf("%d<-",u);
u=h[u];
}
printf("%d\n",s);
printf("%d",t[g]);
break;
}
x[v]=1;
}
free(a);
return 0;
}

Здесь из файла загружается матрица смежности.
Я думал, что максимальный путь можно найти, поменяв кое-что в коде, а именно:

int infinity = 10000 на int infinity = -10000;

, затем строчку

if(x[u]==0 && t[u]>t[v]+a[v][u]) на if(x[u]==0 && t[u]
и строчку

if(x[u]==0 && t[u]w) .

Но это не сработало, программа почти всегда находит максимальные пути неправильно. Возможно, кто-нибудь подскажет, как изменить это код минимального пути на код нахождения максимального?

Максимальный путь в графе

ArdI — Sat, 24 Nov 2007 17:11:55 +0000

ArdI: А что такое максимальный путь ? Можно же несколько типов придумать, я хочу, чтобы вы это и объяснили.

Максимальный путь в графе

mo3r — Sat, 24 Nov 2007 17:06:51 +0000

mo3r:

Цитата ArdI @ 24.11.07, 16:37

Я как раз и говорю о простом пути, а вы о каком ?

Те высказывания справедливы для максимального пути.

Максимальный путь в графе

ArdI — Sat, 24 Nov 2007 16:37:12 +0000

ArdI:

Цитата mo3r @ 22.11.07, 19:59

Цитата ArdI @ 22.11.07, 15:54

Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача.

Да неужели? Алгоритмом Флойда-Уоршелла спокойно ищется максимальный путь или факт его отсутствия (только надо добавить еще одну итерацию для проверки недостижимости), а алгоритмом Дейкстры можно спокойно найти максимальный путь при условии его существования.

А вот максимальный простой путь — это совсем другая задача. И имеет мало общего с тем, о чем было спрошено.

Я как раз и говорю о простом пути, а вы о каком ?

Максимальный путь в графе

Мавроди — Thu, 22 Nov 2007 20:28:09 +0000

Мавроди: Точно...нужно найти максимальный простой путь...

Максимальный путь в графе

mo3r — Thu, 22 Nov 2007 19:59:15 +0000

mo3r:

Цитата ArdI @ 22.11.07, 15:54

Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача.

Максимальный путь в графе

ArdI — Thu, 22 Nov 2007 15:54:31 +0000

ArdI: Никакой Дейкстра и Флойд Варшал тут не помогат, это известная NP задача. не обязательно гамильтонов цикл.

Максимальный путь в графе

Pavlovsky — Thu, 22 Nov 2007 04:49:40 +0000

Pavlovsky: попробуй поиск по ключевой фразе "гамильтонов путь (цикл)".
например http://www.intuit.ru/department/algorithms/gaa/8/gaa_8.html (Алгоритм 2. Поиск гамильтоновых циклов)

Максимальный путь в графе

mo3r — Thu, 22 Nov 2007 04:21:32 +0000

mo3r:

Цитата esperanto @ 21.11.07, 19:31

чушь с позволения сказать

?

Добавлено 22.11.07, 04:22

Цитата esperanto @ 21.11.07, 19:31

чушь с позволения сказать

Да, точно.

Цитата mo3r @ 21.11.07, 19:20

без циклов отрицательного веса

Должно быть без циклов положительного веса.

Максимальный путь в графе

esperanto — Wed, 21 Nov 2007 19:31:09 +0000

esperanto:

Цитата mo3r @ 21.11.07, 19:20

Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса.

чушь с позволения сказать

Максимальный путь в графе

mo3r — Wed, 21 Nov 2007 19:20:43 +0000

mo3r: Можно использовать алгоритм Дейкстры или Флойда-Уоршелла, поменяв там знак у условия: меньше на больше. Только надо отметить, что в неориентированных графах максимального пути не существует, а существует только в ориентированных графах без циклов отрицательного веса.

Максимальный путь в графе

Мавроди — Wed, 21 Nov 2007 17:52:29 +0000

Мавроди: Помогите ребят, горю. Весь нет обыскал - ничего не нашёл(