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

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

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Пара вопросов о рандомайзере и RadioButton http://www.cyberforum.ru/cpp-beginners/thread317896.html
1) srand((unsigned)time(NULL)); int rand_ = rand()%10; rand_ будет равен от 0 до 9 включительно или от 0 до 10 включительно? 2)Есть четыре RadioButton.Как при щелчке по Button1 узнать,была ли выбрана,например,вторая и т.д.(пишу тест).
C++ Поиск одинаковых элементов в 2 массивах Всем привет) Как можно организовать поиск одинаковых элементов в 2 массивах? (сам цикл подскажите пож...) Спасибо заранее) http://www.cyberforum.ru/cpp-beginners/thread317892.html
C++ Нужно разместить переменную по определенному адресу.
Приветствую! Нужно скажем переменную "А" со значение "1" разместить по адресу 0х12345678. Как это реализовать? Заранее премного благодарен!
C++ ошибка Dev-c++
у меня с Dev-c++небльшая проблема.когда я набираю любую программу(будь то проект или source file) и нажимаю "запустить" то он мне выдаёт "Source file(или project) is not compiled."что делать?помогите!!
C++ Почему зацикливается? http://www.cyberforum.ru/cpp-beginners/thread317874.html
Такая программка: #include <conio.h> #include <iostream> #include <windows.h> using namespace std; void strCon(char *str1, char *str2, int len= -1) { if(len== -1) len = strlen(str2);
C++ зашифровать, расшифровать. Здравствуйте, мне нужно вытянуть из программы графические модули, убрать их. По возможности оставить минимальное количество их в программе. Убрать меню, функцию, которая позволяет в программе управлять стрелочками. Готовый код программы имеется, нужно просто сделать то, что я прошу. При запуске программы должно быть все черезвычайно просто. Запустил, вылезло окно с выбором операции. ввел нужно... подробнее

Показать сообщение отдельно
finn-2
0 / 0 / 0
Регистрация: 13.02.2011
Сообщений: 8

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

11.06.2011, 21:29. Просмотров 1530. Ответов 0
Метки (Все метки)

Нужно найти все кратчайшие пути между стартовой и конечной вершиной, которые я задаю. Я воспользовался алгоритмом поиска в ширину, тем самым нашел кратчайшие пути от начальной вершины до всех остальных. Так вот, можно ли достичь поставленной цели с помощью этого алгоритма?
Код 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.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
Текущее время: 15:02. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru