Самый длинный (максимальный) путь в графе - Java SE

[AlexMin]

Подскажите, пожалуйста, как можно изменить алгоритм Дейкстры (Dijkstra), чтобы найти самый длинный путь (наибольшая сумма веса ребер) в графе от определенной стартовой вершины, пройдя ВСЕ вершины. Или какой другой алгоритм можно использовать? Граф без циклов и без ребер с отрицательным весом. Например для графа представленного в виде данной матрицы смежности:

0 1 1 0
1 0 0 1
1 0 0 0
0 1 0 0

Стартовая вершина 1.

На выходе необходимо получить приблизительно в таком формате ответ:

Максимальный путь
1: 1 3
2: 1 2
3: 2 4
Общее время - 3 ед.

Минимальный путь
1: 1 2
2: 1 3 и 2 4
Общее время - 2 ед.
=========================
У меня есть такой какой код:

public class Solution {
    
    private static int INF = Integer.MAX_VALUE / 2;
    
    private int n; //количество вершин в орграфе
    private int m; //количествое дуг в орграфе
    private ArrayList<Integer> adj[]; //список смежности
    private ArrayList<Integer> weight[]; //вес ребра в орграфе
    private boolean used[]; //массив для хранения информации о пройденных и не пройденных вершинах
    private int dist[]; //массив для хранения расстояния от стартовой вершины
    //массив предков, необходимых для восстановления кратчайшего пути из стартовой вершины
    private int pred[]; 
    int start; //стартовая вершина, от которой ищется расстояние до всех других
    
    private BufferedReader cin;
    private PrintWriter cout; 
    private StringTokenizer tokenizer;
    
    //процедура запуска алгоритма Дейкстры из стартовой вершины
    private void dejkstra(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 {
        cin = new BufferedReader(new InputStreamReader(System.in));
        cout = new PrintWriter(System.out);
        tokenizer = new StringTokenizer(cin.readLine());
        
        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>();
        }
        
        //считываем граф, заданный списком ребер
        for (int i = 0; i < m; ++i) {
            tokenizer = new StringTokenizer(cin.readLine());
            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]);
        cout.print((v + 1) + " ");
    }
    
    //процедура вывода данных в консоль
    private void printData() throws IOException {
        for (int v = 0; v < n; ++v) {
            if (dist[v] != INF) {
                cout.print(dist[v] + " ");
            } else {
                cout.print("-1 ");
            }
        }
        cout.println();
        for (int v = 0; v < n; ++v) {
            cout.print((v + 1) + ": ");
            if (dist[v] != INF) {
                printWay(v);
            } 
            cout.println();
        }
                
        cin.close();
        cout.close();
    }
    
    private void run() throws IOException {
        readData();
        dejkstra(start);
        printData();
        
        cin.close();
        cout.close();
    }
    
    public static void main(String[] args) throws IOException {
        Solution solution = new Solution();
        solution.run();
    }
}

[FPaul]

Думаю, что вам нужен алгоритм поиска Гамильтонова пути (не цикла, именно пути). А это по сути полный перебор с запоминанием лучшего варианта.
Т.е. берёте обход в глубину и измняете его под собственные нужды - т.е. когда "погружение" больше невозможно проверяете ситуацию, что все вершины посещены, и если посещены, то запоминаете и лучший результат и путь к его достижению.

Но хочу уточнить. Дело в том, что иногда студенты, изучая алгоритм Дейкстры, изучают и понятие "диаметр графа". Так этот диаметр совершенно не равен длине максимального Гамильтонова пути.

Так вам нужно искать максимальный Гамильтонов путь или диаметр графа?

[AlexMin]

Может я чуть не так написал... в общем мне нужно найти максимальное и минимальное время за которое все элементы графа получат сигнал, при этом за одну единицу времени сигнал могут отправлять n количество НЕ связанных между собой элементов
т.е. на каждом уровне дерева элементы (к котороым уже дошел сигнал) могут работать одновременно.

[FPaul]

Не понял про

Сообщение от AlexMin

при этом за одну единицу времени сигнал могут отправлять n количество

И про то, откуда берётся минимальное и максимальное время.

[AlexMin]

Если сигнал выходит из 1 к 2 это считается как 1 единица времени , за вторую сигнал уже может выходить из 2 и из 1 если у неё есть соединение с какой-то еще вершиной.

Например из графа в примере, минимальное время и лучший вариант - это если сигнал с 1 идет к 2 (одна секунда грубо говоря), а потом одновременно с 2 в 4 и с 1 в 3 (вторая секунда)

Минимальный путь
1: 1 2
2: 1 3 и 2 4
Общее время - 2 ед.

А худший вариант, если сигнал начнет свой путь от 1 к 3 (1 сек), потом от 1 к 2 (вторая сек), потом от 2 к 4 (третья сек).

Максимальный путь
1: 1 3
2: 1 2
3: 2 4
Общее время - 3 ед.

Из одной вершины может идти одновременно 1 сигнал, при этом из разных n количество.

[FPaul]

Эта часть фразы не полностью ясна

Сообщение от AlexMin

Из одной вершины может идти одновременно 1 сигнал, при этом из разных n количество.

Для поиска минимального времени распространения - похоже, что тут задача о потоках, поиске максимального потока.

По максимальному времени. Из примера не ясно, обязательно ли распространение изо всех посещённых вершин или можно на каждом шаге посещать лишь одну новую вершину.
Если требуется обязательное распространение из всех посещённых - то нужно найти диаметр графа (алгоритм Флойда-Уоршелла + поиск в результатах максимального пути = диаметра графа).
Если одновременное распространение не обязательно - то максимальный путь равен (n-1).

Возможно, есть смысл проконсультироваться у преподавателя или получить подсказку из методички (к данной лабораторке).

[AlexMin]

Распространение изо всех посещённых вершин - обязательно. Диаметр графа мне в принципе находит алгоритм Дейкстры (который выше). В данном примере это 2. Это получается минимальный путь для ответа задачи (максимальный 3). А если для например для графа в приложении, то диаметр будет 4. Пока сигнал идет по пути 1 2 8 5 9, из других вершин сигнал идет к другим вершинам.

The best case:
the total time is 4 units of time.

0 1 1 2 3 2 2 2 4 3

1: 1
2: 1 2
3: 1 3
4: 1 2 4
5: 1 2 8 5
6: 1 3 6
7: 1 3 7
8: 1 2 8
9: 1 2 8 5 9
10: 1 3 7 10

А максимальный не будет n-1. А если мы выберем после 1 не 2, а 3 например, то путь может быть длиннее и вот надо найти худший выбор пути.

[FPaul]

Честно - ничего кроме перебора в голову не приходит.
А на каком сайте проверяете? Там нет подсказок в обсуждении?