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

Как найти НЕ Кратчайший путь в графе ?

13.06.2015, 16:12. Показов 1012. Ответов 1
Метки нет (Все метки)

Author24 — интернет-сервис помощи студентам
Мне нужно найти не кратчайший путь в графе от одной вершины к другой, граф неориентированный, задан списком смежности типа:
5
1 1 2
3 2 1 3 4
2 3 2 109
4 4 2 5 7 22
...
где 1 столбец - кол во смежных вершин, 2 столбец - номер вершины, а дальше сами смежные вершины.
В Самом векторе хранятся только номера вершин и смежные с ними, то есть все V[i][0] = №вершины, а уже с V[i][1..] начинаются смежные с данной вершины.
Цель такова, найти РАНДОМНЫЙ, СЛУЧАЙНЫЙ, ПУТЬ, что бы он не был кратчайшим, не важно какой он, может даже и он будет являться кратчайшим если нет других, но смысл в том что бы алгоритм не стоил именно кратчайший путь, вот мои наработки:
1. пытался сделать каким либо обходом тупо(в ширину или в глубину) но как потом восстановить путь ?
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
queue<int> q;
                     int used[500];
                     for ( int i =0 ; i < 500; i++)
                         used[i] = false;
                     int u = s-1;
                     ri1->Text += Convert::ToString(s) + " -> ";
                     while ( u != end )
                     {
                         for ( int i = 1; i < V[u].size(); i ++)
                         {
                             if ( !used[u])
                             {
                                 q.push(V[u][i]-1);
                                 ri1->Text += Convert::ToString(V[u][i]) + " -> ";
                                
                             }
                             else 
                             {
                                  ri1->Text += Convert::ToString(V[u][i]) + " ||\n ";
 
                             }
                         }
                         used[u] = true;
                         u = q.front();
                         q.pop();
                     }
                     ri1->Text += Convert::ToString(end);
2. 2 вариант ...
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
//queue<int> q;
                    Инициализация: есть информация про начальную вершину
                     q.push(start);
                     bool used[500];
                     bool mark[500];
                     for ( int i = 0; i < 500; i++)
                     {
                         used[i] = 0;
                         mark[i] = 0;
                    }
                    used[start] = 0;
                     mark[start] = 1;
                     int u = start;
                     T.resize(T.size()+1);
                     T[T.size()-1] = start;
                     ri1->Text += Convert::ToString(start+1) + " <- ";
                     while (!mark[end])
                     {
                        for ( int i = 1; i < g[u].size(); i++)
                        {
                             if ( !mark[g[u][i]] )
                             {
                                 q.push(g[u][i]);
                                 mark[g[u][i]] = true;
                                 T.resize(T.size()+1);
                                 T[T.size()-1] = g[u][i];
                                 ri1->Text += Convert::ToString(g[u][i]) + " <- ";
                             }
                         }
                         used[u] = true;
                         q.pop();
                         u = q.front();
                     }
помогите пожалуйста найти какой нибудь путь в графе, или дайте идею как это реализовать, потмоу что везде есть инфа только о КРАТЧАЙШИХ путях в графе, а если они не нужны, то что делать ?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
13.06.2015, 16:12
Ответы с готовыми решениями:

Кратчайший путь в графе.
Такая задача: Дан ориентированный взвешенный ациклический граф. Требуется найти в нем кратчайший...

Найдите кратчайший путь в графе
Создайте граф согласно своего варианта в среде С + +, длины путей задайте самостоятельно, найдите...

Кратчайший путь в графе(Рекурсия)
Я реализовал программу с помощью алгоритма флойда.Препод придрался к тому что я реализовал без...

Как найти кратчайший путь на графе?
Задана прямоугольная матрица размера M×N в которой заданы числа. Требуется написать программу,...

1
66 / 66 / 54
Регистрация: 23.09.2012
Сообщений: 212
13.06.2015, 16:38 2
MeGreL,
Поищите алгоритм Йена. Он умеет строить k-ый по длине путь между парой вершин
0
13.06.2015, 16:38
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.06.2015, 16:38
Помогаю со студенческими работами здесь

Найти кратчайший путь в графе
Здравствуйте. Мне необходима помощь в решении курсовой. Необходимо найти кратчайший путь в...

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

С алгоритмом Дейкстра найти кратчайший путь в графе между парой вершин
С помощью алгоритма Дейкстра найти кратчайший путь в графе между парой вершин V0 и V* .

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

Кратчайший путь в графе
Добрый вечер, есть код, но его надо доработать. Не понимаю как и что. Задание: строка ввода # 1: n...

кратчайший путь в графе
делал ли кто нибудь задачу по поиску кратчайшего пути на visual studio 2005? и как его там можно...


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

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

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