Как нужно изменить алгоритм Дейкстры чтобы он искал самый длинный путь?

Question

[Avery007]

Как нужно изменить алгоритм Дейкстры чтобы он искал самый длинный путь?

const
  maxn = 100;
  infinity = maxlongint;

var
  i,j,u,v,n,m,c,min,s,t:longint;
  e,w:array[1..maxn,1..maxn]of longint;
  ne,use,p,d:array[1..maxn]of longint;

begin
  read(n,m,t,s);
  for i:=1 to m do begin
    read(u,v,c);
    inc(ne[v]); e[v,ne[v]]:=u; //edges are inverted
    w[v,u]:=c;
  end;
  for i:=1 to n do d[i]:=infinity;
  d[s]:=0;
  for i:=1 to n do begin
    min:=infinity;
    for j:=1 to n do if (use[j]=0)and(d[j]<min) then begin
      min:=d[j]; u:=j;
    end;
    use[u]:=1;
    for j:=1 to ne[u] do begin
      v:=e[u,j];
      if d[v]>d[u]+w[u,v] then begin
        d[v]:=d[u]+w[u,v]; p[v]:=u;
      end;
    end;
  end;
  writeln(d[t]);
end.

Answer 1

[Mercury13]

Варианты.
1. Если граф циклический, максимальный путь — ∞.
2. Если циклический, но путь обязан быть несамопересекающимся — Дейкстра не подойдёт. Подобную олимпиадную задачу я решал и там решением был перебор с кэшированием (вершин вроде до 15).
3. Если граф циклический, но есть отрицательные веса, которые в определённых случаях дают-таки точный максимум — меняем знак, применяем модификацию Дейкстры для отрицательных весов. Он либо скажет, что есть цикл, позволяющий сколь угодно уменьшить сумму, либо даст точный минимум.
4. Если ациклический ненаправленный — то либо один, либо нет вообще (т.н. лес);
5. Если ациклический направленный — должен работать совсем другой алгоритм: отсортировать в топологическом порядке, убрать те элементы, которые перед началом и за концом, а на оставшихся пустить динамическое программирование.

Answer 2

[Rsa97]

Никак, максимальный путь - бесконечность.