Здравствуйте, помогите разобраться. На вход программе подается граф в виде матрицы смежности. Необходимо найти кратчайшее расстояние от одной точки до другой,и реконструировать этот путь в виде списка вершин, через которые он проходит. Использую я алгоритм Флойда-Уоршелла, алгоритм сам работает, проверил вручную для каждой пары точек,благо их немного. Проблема встает при реконструировании пути, алгоритм которого я, если честно, не до конца понимаю, но все-таки попытался реализовать, т.к. время поджимает, курсовик надо сдавать. Реконструировал путь по принципу, указанному на сайте
http://hci.fenster.name/304y/lab5/ (способ 1). И в 7 случаях из 25 получаю неверные результаты. Помогите, пожалуйста, исправить ошибки и объясните, как же все-таки правильно восстановить путь. Облазил много сайтов, но вот как-то не доходит до меня, как это сделать
Листинг приведен ниже, он довольно нелепый, т.к. это черновой вариант программы и писался для того, чтобы понять все эти алгоритмы и суметь потом встроить все это в более сложный курсовой проект. Здесь довольно много лишних проверок, на которые не стоит обращать внимания, ибо я пока еще дурачок. Главное-придумать как записать путь в виде списка вершин
Заранее спасибо
| Java |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
| 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));
}
} |
|
Если это имеет значение, на вход подается
0 2 0 0 5
2 0 4 0 1
0 4 0 1 2
0 0 1 0 3
5 1 2 3 0
Добавлено через 5 минут
в 86 строке
| Java |
1
| route.add(tops.get(4).get(4)); |
|
создается список,в котором по идее должны храниться вершины. В данном случае для пути из 5 точки в 5.Должно было вывести 5-2(пункт отправления и следующая точка, пункт назначения в список не заносится). Пока что вот так проверял правильность алгоритма.
Листинг приведен ниже, он довольно нелепый, т.к. это черновой вариант программы и писался для того, чтобы понять все эти алгоритмы и суметь потом встроить все это в более сложный курсовой проект. Здесь довольно много лишних проверок, на которые не стоит обращать внимания, ибо я пока еще дурачок. Главное-придумать как записать путь в виде списка вершин 
Заранее спасибо
(
