Как найти Нахождение кратчайшего расстояния на графе с восстановлением пути?

Question

[федор unknown]

Здравствуйте, помогите разобраться. На вход программе подается граф в виде матрицы смежности. Необходимо найти кратчайшее расстояние от одной точки до другой,и реконструировать этот путь в виде списка вершин, через которые он проходит. Использую я алгоритм Флойда-Уоршелла, алгоритм сам работает, проверил вручную для каждой пары точек,благо их немного. Проблема встает при реконструировании пути, алгоритм которого я, если честно, не до конца понимаю, но все-таки попытался реализовать, т.к. время поджимает, курсовик надо сдавать. Реконструировал путь по принципу, указанному на сайте hci.fenster.name/304y/lab5 (способ 1). И в 7 случаях из 25 получаю неверные результаты. Помогите, пожалуйста, исправить ошибки и объясните, как же все-таки правильно восстановить путь. Облазил много сайтов, но вот как-то не доходит до меня, как это сделать Листинг приведен ниже, он довольно нелепый, т.к. это черновой вариант программы и писался для того, чтобы понять все эти алгоритмы и суметь потом встроить все это в более сложный курсовой проект. Здесь довольно много лишних проверок, на которые не стоит обращать внимания, ибо я пока еще дурачок. Главное-придумать как записать путь в виде списка вершин Заранее спасибо

КОД:

package tratata;
 
import java.io.File;
import java.io.FileNotFoundException;
import java.util.*;
/**
 *
 * @author Антон
 */
public class Main {
    public static void main(String[] args) throws FileNotFoundException {
        ArrayList<ArrayList<Integer>> qwa=new ArrayList<ArrayList<Integer>>(); // массив кратчайших путей
        ArrayList<Integer> qwo;
        ArrayList<ArrayList<Integer>> lal=new ArrayList<ArrayList<Integer>>();  // массив весов
        ArrayList<Integer> lol;
        ArrayList<ArrayList<Integer>> tops=new ArrayList<ArrayList<Integer>>(); // массив предков. 
        ArrayList<Integer> top;
        ArrayList<Integer> route=new ArrayList<Integer>(); // список вершин в пути
        Scanner in=new Scanner(new File("lol.txt"));
        Scanner inn=new Scanner(new File("lol.txt"));
        for (int i=0;i<5;i++)    // заполнение lal и tops 
        {
            lol=new ArrayList<Integer>();
            top=new ArrayList<Integer>();
            for (int j=0;j<5;j++)
            {
                top.add(i+1);
                lol.add(in.nextInt());
                System.out.print(lol.get(j));
            }
            System.out.println();
           // qwa.add(lol);
            lal.add(lol);
            tops.add(top);
        }
        System.out.println("вывел считанный lal"); // контролирую ввод, т.к. были с этим небольшие проблемы 
        for (int i=0;i<lal.size();i++)
            System.out.println(lal.get(i));
        System.out.println("Вывел tops");   // массив tops заполняется по алгоритму, указанному на сайте           
        for (int i=0;i<tops.size();i++)          // [url]http://hci.fenster.name/304y/lab5/[/url] 
            System.out.println(tops.get(i));     // реконструирование пути, способ №1
 
        for (int i=0;i<5;i++)
        {
            qwo=new ArrayList<Integer>();
            for (int j=0;j<5;j++)
            {
                qwo.add(inn.nextInt());
                System.out.print(qwo.get(j));
            }
            System.out.println();
           // qwa.add(lol);
            qwa.add(qwo);
        }
        System.out.println("вывел считанный qwa");
        for (int i=0;i<qwa.size();i++)
            System.out.println(qwa.get(i));
 /*       for (int i=0;i<lal.size();i++)
        {
            System.out.println("lal"+lal.get(i));
            System.out.println("qwa"+qwa.get(i));
        }
*/        System.out.println("вывел преобразованный qwa");  // несуществующим ребрам ставим в соотв-ие
        for (int i=0;i<qwa.size();i++)                               // огромное, в рамках задачи, число
        {
            for (int j=0;j<qwa.get(i).size();j++)
            {
                if (qwa.get(i).get(j)==0)
                    qwa.get(i).set(j,999999);
            }System.out.println(qwa.get(i));
        }
        System.out.println("контроль изменения lal");  // проверка чисто для себя, т.к. массив изменялся сам по себе
        for (int i=0;i<lal.size();i++)
            System.out.println(lal.get(i));
        System.out.println("преобразование матрицы кратч путей");
        for (int k=0;k<qwa.size();k++)
        {
            for (int i=0;i<qwa.size();i++)
            {
                for (int j=0;j<qwa.get(i).size();j++)
                {
                    if (qwa.get(i).get(j)>(qwa.get(i).get(k)+qwa.get(k).get(j)))
                    {
                        qwa.get(i).set(j, qwa.get(i).get(k)+qwa.get(k).get(j)); // изменение матр кратч путей
                        tops.get(i).set(j,tops.get(k).get(j));        // заполнение матрицы предков(предыдущ вершин)
                        route.add(tops.get(4).get(4));         // реконструирование пути
                    }
                }
            }
        }
        System.out.println("матрица кратч путей:");
 
        for (int i=0;i<qwa.size();i++)
            System.out.println(qwa.get(i));
        System.out.println("матрица предков");
        for (int i=0;i<tops.size();i++)
            System.out.println(tops.get(i));
        System.out.println("путь:");
        for (int i=0;i<route.size();i++)
            System.out.print(route.get(i));
}
}