0 / 0 / 0
Регистрация: 05.12.2014
Сообщений: 9
1

Алгоритм флойда - уоршелла находит не все пути

23.12.2014, 17:32. Показов 1421. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Пытаюсь реализовать этот алгоритм под c# и unity.

вот создание начальных матриц.
C#
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
           
 
            for (int i = 0; i < Tiles.Length; i++)
            {
                for (int j = 0; j < Tiles.Length; j++)
                {
                    for (int k = 0; k < Tiles[i].GetComponent<Path>().goss.Length; k++)
                    {
                        if (Tiles[i].GetComponent<Path>().goss[k].Equals(Tiles[j]))
                        {
                            if (distance[i, j] == 9999)
                            {
                                distance[i, j] = 0;
                            }
                            distance[i, j] += Tiles[i].GetComponent<Path>().ves;
                            history[i, j] = j;
                            break;
                        }
                        distance[i, j] = 9999;
                        history[i, j] = -1;
                        if (i == j) distance[i, j] = 0;
 
                    }
                }
 
            }
создаются два массива, вывел их в тхт Distance.txt History.txt

потом пытаюсь найти пути:
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
            for (int a = 0; a < Tiles.Length; a++)
            {
                for (int b = 0; b < Tiles.Length; b++)
                {
                    if (distance[a, b] != 9999)
                    {
                        for (int c = 0;c < Tiles.Length; ++c)
                        {
                            if (distance[a, c] > distance[a, b] + distance[b, c])
                            {
                                distance[a, c] = distance[a, b] + distance[b, c];
                                history[a, c] = history[a, b];
                            }
                        }
                    }
                }
            }
получаются такие массивы Distance1.txt History1.txt


пути находит не из всех во все, где я накосячил?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
23.12.2014, 17:32
Ответы с готовыми решениями:

Алгоритм Флойда — Уоршелла. Как же найти путь?
Реализовал нахождение длин кратчайшего пути между вершинами, но как найти сам путь так и не смог...

Алгоритм Флойда-Уоршелла [для нахождения кратчайших путей]
Дан ориентированный взвешенный граф. По его матрице смежности нужно для каждой пары вершин...

Печать кратчайшего пути из матрицы последовательности вершин (Алгоритм флойда)
Здравствуйте, проблема следующая: не могу получить список вершин из результирующей матрицы. В...

Восстановление пути по матрице, возвращаемой алгоритмом Флойда - Уоршелла
Делаю, алгоритм флойда-уоршелла, делаю сам на делфи, но исходники с решением моей проблемы (ну по...

3
0 / 0 / 0
Регистрация: 05.12.2014
Сообщений: 9
23.12.2014, 17:41  [ТС] 2
вот сам граф
Алгоритм флойда - уоршелла находит не все пути
0
0 / 0 / 0
Регистрация: 05.12.2014
Сообщений: 9
23.12.2014, 18:14  [ТС] 3
исправил алгоритм поиска пути
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
            for (int i = 0; i < Tiles.Length; ++i)
            {
                for (int a = 0; a < Tiles.Length; ++a)
                {
                    for (int b = 0; b < Tiles.Length; ++b)
                    {
                        if (distance[a, b] != 9999)
                        {
                            for (int c = 0; c < Tiles.Length; ++c)
                            {
                                if (distance[a, c] > distance[a, b] + distance[b, c])
                                {
                                    distance[a, c] = distance[a, b] + distance[b, c];
                                    history[a, c] = history[a, b];
                                }
                            }
                        }
                    }
                }
так работает, но везде пишут что цикла должно быть 3. так что вопрос на повестке(
0
0 / 0 / 0
Регистрация: 05.12.2014
Сообщений: 9
24.12.2014, 20:06  [ТС] 4
решил таки, объяснил преподаватель, оказалось как промежуточную вершину нужно использовать внешний цикл

C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
 for (int i = 0; i < Tiles.Length; i++)
            {
                for (int a = 0; a < Tiles.Length; a++)
                {
                    for (int b = 0; b < Tiles.Length; b++)
                    {
 
                        if (distance[a, i] < 9999 && distance[i, b] < 9999)
                        {
                            if (distance[a, b] > distance[a, i] + distance[i, b])
                            {
                                distance[a, b] = Math.Min(distance[a, b], distance[a, i] + distance[i, b]);
                                history[a, b] = i;
                            }
                        }
 
                    }
                }
            }
0
24.12.2014, 20:06
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
24.12.2014, 20:06
Помогаю со студенческими работами здесь

Алгоритм Флойда - Уоршелла
не получается реализовать алгоритм Флойда-Уоршелла, вроде все должнен выводить, а выводит или нули...

Алгоритм Флойда-Уоршелла
Вечно какая-то засада и кругом враги! :-) Разбирался я в алгоритме Уоршелла. И вот какая проблема:...

Алгоритм Флойда-Уоршелла
Народ подскажите , а как реализовать этот алгоритм на Delphi ?

Алгоритм Флойда–Уоршелла
for (int k=0; k&lt;n; k++) for (int i=0; i&lt;n; i++) for (int j=0; j&lt;n; j++)как сделать так,...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
4
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru