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

Алгоритм Флойда

19.11.2017, 22:20. Показов 4918. Ответов 2
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Добрый день , помогите разобраться с алгоритмом работает частично , не все пути рассчитывает корректно
пример:
(3,5) -> путь 5-8-4-2-3 // посчитан верно
(3,7)-> путь 3-6-7 //рассчитан верно
а вот (7,5) -> путь 5-8-6-7 // рассчитан не правильно, должно было получиться "5-8-4-2-3-6-7"
подскажите где ошибся не как не могу понять
вот алгоритм
входной граф - mat(изображение исходного графа прикрепил расстояние ="1" если есть связь меж вершинами значит есть путь в обе стороны, матрица квадратная ); mat_p - матрица для восстановления решения
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 int[,] mat =    {{0,1,1,0,0,0,0,0,0,0,0},
                             {1,0,0,0,0,0,0,0,0,0,0},
                             {1,0,0,1,1,0,0,0,0,0,0},
                             {0,0,1,0,0,0,1,0,0,1,0},
                             {0,0,1,0,0,0,0,0,1,0,1},
                             {0,0,0,0,0,0,0,0,1,0,0},
                             {0,0,0,1,0,0,0,1,0,0,0},
                             {0,0,0,0,0,0,1,0,0,0,0},
                             {0,0,0,0,1,1,0,0,0,0,0},
                             {0,0,0,1,0,0,0,0,0,0,0},
                             {0,0,0,0,1,0,0,0,0,0,0}};
 
            int[,] mat_p =  {{0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0},
                             {0,0,0,0,0,0,0,0,0,0,0}};
если значение "0" то значение максимального пути и все диагональные элементы = "0"

C#
1
2
3
4
5
6
7
  for (int i = 0; i < Math.Sqrt(mat_p.Length); i++)
                for (int j = 0; j < Math.Sqrt(mat_p.Length); j++)
                {
                    if (mat[i, j] == 0)
                        mat[i, j] = 10000;
                    if (i == j) mat[i, j] = 0;
                }
подготовка матрицы восстановления пути

C#
1
2
3
4
5
6
7
8
9
10
11
 for(int i =0; i<Math.Sqrt(mat_p.Length);i++)
                for (int j = 0; j < Math.Sqrt(mat_p.Length); j++)
                {
                    if (mat[i, j] == 10000 )
                        mat_p[i, j] = 10000;
                    else
                    {
                        mat_p[i, j] = j;
                        if (i == j) mat_p[i, j] = 0;
                    }
                }
C#
1
2
3
4
5
6
7
            puth(mat, mat_p);
            print_mt(mat);
            print_mt(mat_p);
            int a = 5;
            int b =7;
            
            red_path(a, b, mat_p);
основной метод расчета кратчайшего пути
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
private void puth(int[,] m, int [,] mp)
        {
            for (int k = 0; k < Math.Sqrt(m.Length); ++k)
            {
                for (int i = 0; i < Math.Sqrt(m.Length); ++i)
                {
                    for (int j = 0; j < Math.Sqrt(m.Length); ++j)
                    {
                        if (m[i, j] > m[i,k]+m[k,j])
                        {
                            m[i, j] = m[i, k] + m[k, j];
                            mp[i, j] = k;
                        }                       
                    }
                }
            }
        }
метод восстановления пути
C#
1
2
3
4
5
6
7
8
9
10
 private void red_path(int a, int b, int [,] m)
        {
            if (a == b) { System.Diagnostics.Debug.WriteLine("-> {0}", b); return; }
            else
            {
                System.Diagnostics.Debug.WriteLine("-> {0}", b);
                red_path(a, m[b, a], m);
                return;
            }
        }
вывод матрицы
C#
1
2
3
4
5
6
7
8
9
10
11
 public void print_mt(int[,] _m)
        {
            double t =Math.Sqrt(_m.Length);
            for (int i = 0; i < Math.Sqrt(_m.Length); i++)
            {
                System.Diagnostics.Debug.WriteLine("");
                for (int j = 0; j < Math.Sqrt(_m.Length); j++)
                    System.Diagnostics.Debug.Write(" " + _m[i, j]);
            }
            System.Diagnostics.Debug.WriteLine("\n**********************************");
        }
Изображения
 
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
19.11.2017, 22:20
Ответы с готовыми решениями:

Алгоритм флойда
Здравствйте у меня есть беда. Есть вот такой код по вычеслению кратчайших путей и запоминание...

Реализовать алгоритм Флойда-Уоршалла
Здравствуйте. Я понимаю, что уже неоднократно разбирался алгоритм Флойда-Уоршалла, но у меня всё...

Правильный ли алгоритм Флойда в следующем примере
///&lt;$50 summary&gt; ///MICROSOFT STUDIO LIVE.com =&gt; Алгоритм Флойда ///&lt;!summary $50&gt; using...

Вывести алгоритм флойда с выводом на печать кратчайших путей
Вообщем нужно на си-шарп вывести алгоритм флойда с выводом на печать кратчайших путей , а матрица...

2
907 / 664 / 318
Регистрация: 23.10.2016
Сообщений: 1,543
19.11.2017, 23:48 2
У вас в mat_p[i, j] записывается номер любой вершины, через которую проходит кратчайший путь из i в j. В частности, может быть, что mat_p[5, 7] = 8. Соответственно все вершины между 8-й и 7-й в этом случае потеряются.

Добавлено через 16 минут
C#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void red_path(int a, int b, int[,] m)
{
    red_path_impl(a, b, m);
    System.Diagnostics.Debug.Write($"-> {b}");
}
 
void red_path_impl(int a, int b, int[,] m)
{
    if (a == b || mat[a, b] == 1)
    {
        System.Diagnostics.Debug.Write($"-> {a}");
        return;
    }
    
    int k = m[a, b];
    red_path_impl(a, k, m);
    red_path_impl(k, b, m);
}
Предварительное заполнение матрицы mat_p следует удалить.
1
1 / 1 / 0
Регистрация: 24.01.2013
Сообщений: 85
20.11.2017, 06:15  [ТС] 3
Спасибо , все работает
0
20.11.2017, 06:15
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
20.11.2017, 06:15
Помогаю со студенческими работами здесь

Алгоритм флойда для поиска кратчайших путей в графе
алгоритм флойда для поиска кратчайших путей в графе. Вывожу длину путей между вершинами, не могу...

Построение кратчайших путей между всеми парами вершин графа. Алгоритм Флойда
Взялся за свой курсовик. Задача такая: Реализовать алгоритм Флойда для построения кратчайших путей...

Поиск вершины в графе по алгоритму Флойда
Добрый час суток! Есть такая задача : Написать программу в которой будет выполняться алгоритм...

Алгоритм Флойда
Помогите переделать программу вот нашел #include &lt;iostream&gt; const int inf=1E9; using namespace...


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

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

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