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

Вывести алгоритм флойда с выводом на печать кратчайших путей

09.04.2014, 21:43. Показов 5117. Ответов 3
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Вообщем нужно на си-шарп вывести алгоритм флойда с выводом на печать кратчайших путей , а матрица стоимостей задается ортогональным списком. Помогите реализовать .
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.04.2014, 21:43
Ответы с готовыми решениями:

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

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

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

[Теория графов] Составить программу Нахождения кратчайших путей между всеми парами вершин графа по алгоритму Флойда-Уоршелла
Здравствуйте! Нужно составить алгоритм(схема и описание алгоритма) и программу Нахождения...

3
1057 / 864 / 195
Регистрация: 31.03.2010
Сообщений: 2,521
10.04.2014, 11:46 2
WebDiRu, 1) создаем двумерный W массив и загоняем в него длины ребер W[i,j] = длина ребра от i до j, иначе Int32.MaxValue
2) используем алгоритм:
C#
1
2
3
4
for(int k = 1; k< n; k++)
  for(int i = 0; i< n; i++)
   (int j = 1; j< n; j++)
      W[i][j] = Math.Min(W[i][j], W[i][k] + W[k][j])
3) выводим матрицу
с чем трудности?
0
0 / 0 / 0
Регистрация: 09.04.2014
Сообщений: 12
10.04.2014, 22:15  [ТС] 3
Я разобрался в самом алгоритме и его выводе. Я не знаю , как задать матрицу стоимостей через ортогональные списки. Я знаю , что такое линейные , а вот ортогональные понять не могу.

Добавлено через 23 секунды
Learx, Я разобрался в самом алгоритме и его выводе. Я не знаю , как задать матрицу стоимостей через ортогональные списки. Я знаю , что такое линейные , а вот ортогональные понять не могу.

Добавлено через 4 минуты
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
27
28
29
30
31
32
33
34
35
36
37
using System;
namespace Алгоритм_Флойда
{
    class Program
    {
        static void Main()
        {
            int[,] array = new int[6, 6] // Создание двумерного массива 6x6
            //Матрица смежности для применения Алгоритма Флойда
           {{0,3,1000,3,6,1000},
            {1000,0,4,7,1000,4},
            {3,8,0,5,1000,2},
            {1000,6,1000,0,3,1000},
            {7,1000,1,4,0,4},
            {5,2,1000,1000,2,0}};
 
            int i, j, k; // Создание локальных переменных для вычисления
 
            // Применение алгоритма Флойда с использованием матрицы смежности
            for (k = 0; k < 6; k++)
                for (i = 0; i < 6; i++)
                    for (j = 0; j < 6; j++)
                        if (array[i, j] > array[i, k] + array[k, j])
                            array[i, j] = array[i, k] + array[k, j];
 
            // Вывод измененной матрицы смежности на экран
            Console.WriteLine("Алгоритм Флойда : ");
            for (i = 0; i < 6; i++)
            {
                for (j = 0; j < 6; j++)
                    Console.Write(array[i, j] + "\t");
                Console.WriteLine();
            }
            Console.ReadLine();
        }
    }
}
Есть вот этот код , как его преобразовать для ортогональных списков?
0
1057 / 864 / 195
Регистрация: 31.03.2010
Сообщений: 2,521
11.04.2014, 19:37 4
WebDiRu,
1) идем по списку
1.1) получаем первое число - это ряд массива
1.2) идем по ряду
1.2.1) получаем пару вершина-расстояние(или как там у вас задан ортогональный список)
1.2.2) полученная вершина - столбец, расстояние значение ячейки
1.3) для всех остальных значений в ряду ставим Int32.MaxValue
0
11.04.2014, 19:37
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
11.04.2014, 19:37
Помогаю со студенческими работами здесь

Поиск кратчайших путей в графе. Алгоритм Данцига
Есть ли у кого-то хороший источник с информацией по данному методу/алгоритму? Желательно с...

Поиск кратчайших путей из одной вершины (алгоритм Дейкстры)
Алгоритм Дейкстры . Поиск кратчайших путей из одной вершины. Три файла h, сpp, main (в мэйне тесты/...

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

Нахождение количества кратчайших путей
собственно, то задачка: Шпиону требуется пробраться из одной клетки лабиринта в другую. У шпиона...


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

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

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