Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.50/4: Рейтинг темы: голосов - 4, средняя оценка - 4.50
gwalex11
0 / 0 / 0
Регистрация: 12.06.2014
Сообщений: 11
1

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

13.05.2017, 13:09. Просмотров 785. Ответов 10
Метки нет (Все метки)

Добрый день всем!
Такая казалось бы тривиальная задача для гуру программистов, но ничего толкового не могу найти.
Нужно найти несколько кратчайших путей (то есть топ 3 кратчайших пути: самый кратчайший потом из оставшихся кратчайшие пути) в графе (матрица смежности задается вручную и начальная и конечная вершины), нужно вывести эти вершины кратчайших путей. Можно использовать любой алгоритм (A*, дейкстры, флойда...). Можно также с помощью delphi, pascal
Код из этой темы показался более похожим, но не выполняющим задачу алгоритма:
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
38
39
40
41
42
43
44
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
 
namespace Алгоритм_Флойда
{
    class Program
    {
        static void Main()
        {
            int[,] array = new int[6, 6] 
 
{{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("Алгоритм Флойда : ");
            Console.WriteLine("   1 2 3 4 5 6");
            Console.WriteLine(" _____________");
 
            for (i = 0; i < 6; i++)
            {
                Console.Write((i + 1) + "| ");
                for (j = 0; j < 6; j++)
                    Console.Write("{0} ", array[i, j]);
                Console.WriteLine("\n |");
            }
            Console.ReadLine();
        }
    }
}
Заранее спасибо!

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь.

0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.05.2017, 13:09
Ответы с готовыми решениями:

Поиск путей в графе
Стоит задача найти все пути на графе. Так, чтобы не было таких путей, в которых множество вершин...

поиск путей на графе
поиск путей на графе дан ориентированый граф из 2-50 вершин, где каждому существующему ребру...

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

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

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

10
ROS88
131 / 130 / 99
Регистрация: 10.03.2015
Сообщений: 536
13.05.2017, 19:18 2
Цитата Сообщение от gwalex11 Посмотреть сообщение
Нужно найти несколько кратчайших путей
Объясни подробнее, тебе необходимо найти кратчайший маршрут, проходящий через все вершины графа, или через две заданные пользователем вершины?
0
gwalex11
0 / 0 / 0
Регистрация: 12.06.2014
Сообщений: 11
13.05.2017, 19:39  [ТС] 3
Нужно найти так сказать топ-3 кратчайших маршрута (самый короткий, подлиннее и ещё подлиннее предыдущего) маршрут между заданными точками (начало) и (конец)
0
ROS88
131 / 130 / 99
Регистрация: 10.03.2015
Сообщений: 536
13.05.2017, 19:47 4
Цитата Сообщение от gwalex11 Посмотреть сообщение
маршрут между заданными точками (начало) и (конец)
То есть, если граф состоит из пяти вершин, то необходимо найти кратчайшие маршруты между вершиной номер один и вершиной номер пять?
0
13.05.2017, 19:47
gwalex11
0 / 0 / 0
Регистрация: 12.06.2014
Сообщений: 11
13.05.2017, 19:58  [ТС] 5
Совершенно верно
0
ROS88
131 / 130 / 99
Регистрация: 10.03.2015
Сообщений: 536
13.05.2017, 20:03 6
Еще один вопрос. Заданный граф всегда полностью связный? Или существуют вершины, не соединенные ребром?
0
gwalex11
0 / 0 / 0
Регистрация: 12.06.2014
Сообщений: 11
13.05.2017, 20:07  [ТС] 7
Всегда связанный, даже больше скажу ориентированный и вот ссылка на него http://graphonline.ru/?graph=tkoTPwQkIGxkuSeu
0
ROS88
131 / 130 / 99
Регистрация: 10.03.2015
Сообщений: 536
13.05.2017, 20:11 8
Цитата Сообщение от gwalex11 Посмотреть сообщение
вот ссылка на него
Честно говоря по указанной выше ссылке никакого графа не нашел!!!
0
gwalex11
0 / 0 / 0
Регистрация: 12.06.2014
Сообщений: 11
13.05.2017, 20:16  [ТС] 9
Да я сам что то не понял в чем дело, http://iscr.ru/image/EheVZ вот скрин графа с сайта с путём
0
ROS88
131 / 130 / 99
Регистрация: 10.03.2015
Сообщений: 536
13.05.2017, 20:36 10
Для решения задачи такого типа можно воспользоваться датчиком случайных чисел. То есть, на первом этапе, среди вершин с номерами 2, 3, 4, ... (вершина с номером один является начальной, поэтому ее выбирать не нужно) случайным образом выбираем по одной вершине и запоминаем их последовательность. Заметим, что в дальнейшем данная последовательность будет считаться как оптимальный маршрут. Для этого маршрута рассчитываем расстояние и также запоминаем ее. После этого, процедуру повторяем, например сто раз. Среди полученных результатов выбираем три кратчайшие маршруты и выводим их. Это как вариант.
0
oldnewyear
419 / 416 / 158
Регистрация: 21.05.2016
Сообщений: 1,325
13.05.2017, 21:57 11
https://en.wikipedia.org/wiki/K_shortest_path_routing
https://en.wikipedia.org/wiki/Yen%27s_algorithm
https://www.ics.uci.edu/~eppstein/pubs/Epp-SJC-98.pdf
1
13.05.2017, 21:57
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.05.2017, 21:57

Экономное представление путей в графе
Есть приведенное бинарное дерево (изоморфные подграфы сливаются, в узла может стать несколько...

Каким образом лучше выполнять поиск всех возможных путей в ориентированном графе?
Имеется ориентированный граф. Каждое ребро графа имеет вес (условно обозначу #). Задача - найти...

Поиск в графе
Здравствуйте, есть следующая задача: Дан массив A длины (n+1), содержащий натуральные числа от 1...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru