How should Dijkstra's algorithm be modified so that it looks for the longest path?

Question

Pascal

How should Dijkstra's algorithm be modified so that it looks for the longest path?

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

Options.
1. If the graph is cyclic, the maximum path is ∞.
2. If the path is cyclic, but the path must be non-self-intersecting, Dijkstra will not work. I solved a similar Olympiad problem, and there the solution was enumeration with caching (like up to 15 vertices).
3. If the graph is cyclic, but there are negative weights, which in certain cases give the same exact maximum, change the sign, apply Dijkstra's modification for negative weights. He will either say that there is a cycle that allows you to arbitrarily reduce the amount, or he will give an exact minimum.
4. If acyclic undirected - then either one or not at all (the so-called forest);
5. If it is acyclic directed, a completely different algorithm should work: sort in topological order, remove those elements that are before the beginning and after the end, and start dynamic programming on the remaining ones.

Answer 2

No, the maximum path is infinity.