Floyd-Warshall для наибольшего расстояния для ненаправленного графа

Question

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

1. Я добавляю отрицательные веса вместо положительных.

2. Тогда я узнаю кратчайший путь.

Но это не дает мне правильный вывод. Может кто-то указать на ошибку, которую я делаю.

class TestClass {
    public static void main(String args[] ) throws Exception {
        Scanner sc = new Scanner(System.in);
        int testcases=sc.nextInt();
        for(int t=0;t<testcases;t++)
        {
            int nodes=sc.nextInt();
            int edges=sc.nextInt();
            int[][] dist_mat=new int[nodes][nodes];
            for(int i=0;i<nodes;i++)
            {
                for(int j=0;j<nodes;j++)
                {
                    if(i!=j)
                    {
                        dist_mat[i][j]=Integer.MAX_VALUE;
                    }
                }
            }
            for(int i=0;i<edges;i++)
            {
                int source=sc.nextInt();
                int dest=sc.nextInt();
                dist_mat[source-1][dest-1]=-sc.nextInt();
                dist_mat[dest-1][source-1]=dist_mat[source-1][dest-1];
            }

            for(int k=0;k<nodes;k++)
            {
                for(int i=0;i<nodes;i++)
                {
                    for(int j=0;j<nodes;j++)
                    {

                        if(i!=j && j!=k && i!=k && dist_mat[i][j]>dist_mat[i][k]+dist_mat[k][j])
                        {
                            if(dist_mat[i][k]<Integer.MAX_VALUE && dist_mat[k][j]<Integer.MAX_VALUE)
                                    dist_mat[i][j]=Integer.min(dist_mat[i][j],dist_mat[i][k]+dist_mat[k][j]);
                            if(dist_mat[j][k]<Integer.MAX_VALUE && dist_mat[k][i]<Integer.MAX_VALUE)
                                    dist_mat[j][i]=Integer.min(dist_mat[j][i],dist_mat[j][k]+dist_mat[k][i]);
                        }

                    }
                }
            }   
        }
    }

Тот же вход:

1[количество тестовых случаев]

5 4 [количество узлов, количество ребер]

1 2 4 [первый узел, второй узел, вес]

3 2 3 [первый узел, второй узел, вес]

2 5 2 [первый узел, второй узел, вес]

4 1 1[первый узел, второй узел, вес]

Answer 1

Флойд-Варшал должен работать. Сначала обратите внимание, что существует путаница, когда люди говорят о самой длинной проблеме расстояния и ее NP-твердости.

По этой ссылке:

обратите внимание, что существует огромная путаница, когда мы говорим о самом длинном пути:

Проблема самого длинного пути обычно означает поиск самого длинного простого пути. Проблема кратчайшего пути, однако, фокусируется на поиске кратчайшего (простого или непростого) пути.

Если исходный график G не имеет положительного цикла, то -Gу графа, созданного из G путем отрицания его ребер, не будет отрицательных ребер, и вы МОЖЕТЕ использовать Floyd-Warshall, чтобы найти кратчайший путь в -Gи, следовательно, самый длинный путь в G, Поэтому Floyd-Warshall должен работать, если ваш входной граф не имеет положительных циклов. Также смотрите здесь.

Одна из возможных проблем с вашим кодом заключается в том, что вы инициализируете все расстояния до значения MAX: dist_mat[i][j]=Integer.MAX_VALUEв то время как я думаю, что во Флойд-Варшалле вы должны инициализировать их для весов ребер графа.

Answer 2

Алгоритм, который мог бы найти самый длинный путь между любыми двумя узлами, мог бы быть использован для решения задачи о гамильтоновом пути. Однако задача о гамильтоновом пути является NP-полной. Алгоритм Флойда-Варшалла дает ограничение полиномиального времени выполнения, поэтому не похоже, что модификация приведет к алгоритму, который определяет самые длинные пути.