How can you change Dijkstra's algorithm (Dijkstra) to find the longest path (the largest sum of edge weights) in the graph from a certain starting vertex, passing all the vertices. Or what other algorithm can I use? Count without cycles and without edges with negative weight. For example, for a graph represented in the form of a given adjacency matrix:

0 1 1 0

1 0 0 1

1 0 0 0

0 1 0 0

Starting Top 1.

At the output, you need to get approximately in this format the answer:

The worst case scenario:

  1. 1-> 3 (1 unit of time)
  2. 1-> 2 (1 unit of time)
  3. 2-> 4 (1 unit of time) The total time is 3 units of time

The best case scenario:

  1. 1-> 2 (1 unit of time)
  2. 1-> 3 and2-> 4 (1 unit of time) The total time is 2 units of time.

I have the following Dijkstra algorithm code:

public class Dij { private static int INF = Integer.MAX_VALUE / 2; protected int n; //количество вершин в орграфе protected int m; //количествое дуг в орграфе private ArrayList<Integer> adj[]; //список смежности private ArrayList<Integer> weight[]; //вес ребра в орграфе private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах private int dist[]; //массив для хранения расстояния от стартовой вершины private int pred[]; //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины int start; //стартовая вершина, от которой ищется расстояние до всех других private StringTokenizer tokenizer; Result res; protected String p; protected String k; //процедура запуска алгоритма Дейкстры из стартовой вершины private void Dijkstra(int s) { dist[s] = 0; //кратчайшее расстояние до стартовой вершины равно 0 for (int iter = 0; iter < n; ++iter) { int v = -1; int distV = INF; //выбираем вершину, кратчайшее расстояние до которого еще не найдено for (int i = 0; i < n; ++i) { if (used[i]) { continue; } if (distV < dist[i]) { continue; } v = i; distV = dist[i]; } //рассматриваем все дуги, исходящие из найденной вершины for (int i = 0; i < adj[v].size(); ++i) { int u = adj[v].get(i); int weightU = weight[v].get(i); //релаксация вершины if (dist[v] + weightU < dist[u]) { dist[u] = dist[v] + weightU; pred[u] = v; } } //помечаем вершину v просмотренной, до нее найдено кратчайшее расстояние used[v] = true; } } //процедура считывания входных данных с консоли private void readData() throws IOException { tokenizer = new StringTokenizer(k); n = Integer.parseInt(tokenizer.nextToken()); //считываем количество вершин графа m = Integer.parseInt(tokenizer.nextToken()); //считываем количество ребер графа start = Integer.parseInt(tokenizer.nextToken()) - 1; //инициализируем списка смежности графа размерности n adj = new ArrayList[n]; for (int i = 0; i < n; ++i) { adj[i] = new ArrayList<Integer>(); } //инициализация списка, в котором хранятся веса ребер weight = new ArrayList[n]; for (int i = 0; i < n; ++i) { weight[i] = new ArrayList<Integer>(); } tokenizer = new StringTokenizer(p); //считываем граф, заданный списком ребер for (int i = 0; i < m; ++i) { int u = Integer.parseInt(tokenizer.nextToken()); int v = Integer.parseInt(tokenizer.nextToken()); int w = Integer.parseInt(tokenizer.nextToken()); u--; v--; adj[u].add(v); weight[u].add(w); } used = new boolean[n]; Arrays.fill(used, false); pred = new int[n]; Arrays.fill(pred, -1); dist = new int[n]; Arrays.fill(dist, INF); } //процедура восстановления кратчайшего пути по массиву предком void printWay(int v) { if (v == -1) { return; } printWay(pred[v]); res.answ.append(new String((v + 1) + " ")); } //процедура вывода данных в консоль private void printData() throws IOException { //Calculate units of time int max = 0; int min = 0; for(int i = 0; i<dist.length; i++){ if(max<dist[i]) max = dist[i]; if(min>dist[i]) min = dist[i]; } res.answ.setText("The best case: \nthe total time is " + max + " units of time.\n\n"); for (int v = 0; v < n; ++v) { if (dist[v] != INF) { res.answ.append(new String(dist[v] + " ")); } else { res.answ.append(new String("No ")); } } res.answ.append("\n\n"); for (int v = 0; v < n; ++v) { res.answ.append(new String((v + 1) + ": ")); if (dist[v] != INF) { printWay(v); } res.answ.append(new String("\n")); } } public void run() throws IOException { res = new Result(); readData(); Dijkstra(start); printData(); } }

    1 answer 1

    In the general case, the problem is NP-hard, but in the case when the graph is oriented and acyclic, the problem is solved in a time linear in the number of edges. It is necessary to replace the weight of the ribs with the opposite (plus the minus) and look for the shortest path in the graph. In principle, you can use Dijkstra's algorithm (working per square of the number of vertices), but you can use simpler algorithms due to acyclicity.

    For example, we perform topological sorting: we arrange all vertices in one line so that all edges go strictly from left to right (the first two pictures below).

    Then we go through the vertices in turn and for each vertex u , for each edge (u,v) we do something like

     if (dist[v] < dist[u] + weight(u, v)) dist[v] = dist[u] + weight(u, v)

    Picture

    I took a picture and a piece of code here . In the same place under the link there is a ready code.

    • Maybe I almost wrote wrong ... in general, I need to find the maximum and minimum time for which all elements of the graph will receive a signal, while for one unit of time a signal can be sent n number of NOT connected elements at each level of the tree, elements (to which the signal has already reached) can operate simultaneously. - Alex
    • Well, zashib now :) I answered the question you asked, and if you set it “slightly” wrong, that it turned into a completely different task, then it’s somehow even indecent. - Zealint