Форум программистов, компьютерный форум CyberForum.ru

Поиск всех кратчайших путей в графе - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
finn-2
0 / 0 / 0
Регистрация: 13.02.2011
Сообщений: 8
11.06.2011, 21:29     Поиск всех кратчайших путей в графе #1
Нужно найти все кратчайшие пути между стартовой и конечной вершиной, которые я задаю. Я воспользовался алгоритмом поиска в ширину, тем самым нашел кратчайшие пути от начальной вершины до всех остальных. Так вот, можно ли достичь поставленной цели с помощью этого алгоритма?
Код java, но тут все то же самое, что C++, кроме вывода.
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
//Кратчайшие пути содержатся в массиве Label
//Graph =new int [size][size];матрица смежности графа с size вершин, заполняется до вызова функции
public void BFS_search() {        
        int k, p, cur, Start = 0;
        Label = new int[size]; //Массив меток
        FIFO = new int[size];//Очередь
        for (int i = 0; i < size; i++) {
            FIFO[i] = 0;
            Label[i] = 32767;
        }
        p = 0;//указатель на начало очереди
        k = 1;//указатель на конец очереди
        FIFO[p] = Start;//заносит стартовую вершину в очередь
        Label[Start] = 0;//помечает ее меткой 0
        while (p != k) {
            cur = FIFO[p];//выделяет вершину из очереди
            p++;//сдвигает указатель начала на единицу
            for (int i = 0; i < size; i++) {
                if (Graph[cur][i] == 1 && Label[i] > Label[cur] + 1) {
                    //lst.add(cur+"-"+i+" ");
                    FIFO[k] = i;//заносит вершину в очередь
                    k++;//сдвигает указатель конца очереди
                    Label[i] = Label[cur] + 1;//помечает вершину
                }
            }
        }
        for (int i = 0; i < size; i++) {//вывод результата
            System.out.print(i + "-" + Label[i] + " ");
        }
        System.out.println();
}
Добавлено через 3 часа 7 минут
Да и еще. Все ребра графа имеют одинаковую длину, равную 1.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.06.2011, 21:29     Поиск всех кратчайших путей в графе
Посмотрите здесь:

C++ Поиск кратчайших путей из одного источника для неориентированного графа
C++ Поиск кратчайших путей между двумя вершинами графа методом Шимбела.
C++ Обход всех путей в графе
C++ Прогрмма по поиску кратчайших путей в графе
Реализация алгоритма А* (поиск кратчайших расстояний на графе) C++
Нахождение всех путей в графе от одной вершины до другой обходом в ширину C++
Поиск всех различных путей в графе C++
C++ Поиск кратчайших путей в графе

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

Текущее время: 02:08. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru