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

Кратчайший путь до определённой вершины графа - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ отладчик mpi кластера в VS 2013 http://www.cyberforum.ru/cpp-beginners/thread1755420.html
делал по инструкции https://msdn.microsoft.com/ru-ru/library/ee441265.aspx#BKMK_debugMany до момента, когда сказано "В группе Загружаемый отладчик выберите элемент Отладчик MPI-кластера." Однако у...
C++ Не работает команда Вроде бы всё правильно сделал, но не работает команда "Получение матрицы" Вот код Файл: Spisok.h #pragma once class Spisok { int size1; int size2; int **mas; http://www.cyberforum.ru/cpp-beginners/thread1755417.html
Нужны комментарии к программе C++
Прошу помогите понять, что происходит в каждой строке этих двух программ? То есть помогите к каждой строке написать комментарии пожалуйста?? 1 программа: #include <iostream> #include <cstdlib>...
Ошибка в программу C++
Здравствуйте, изучаю полиморфизм, пишу программу, столкнулся с такой ошибкой. Имеется абстрактный класс, 3 дочерних. Figure.h #pragma once //Структура для хранения точек struct Point{ int...
C++ Разработать класс Person, который содержит соответствующие члены для хранения. http://www.cyberforum.ru/cpp-beginners/thread1755389.html
Разработать класс Person, который содержит соответствующие члены для хранения: -имени, -возраста, -пола и -телефонного номера. Сделайте поля класса закрытыми и обеспечите открытые методы...
C++ Записная книжка с сохранением и чтением текстового файла Записная книжка с сохранением и чтением текстового файла.. Помогите чем кто может, заранее спасибо:) подробнее

Показать сообщение отдельно
dimsum
0 / 0 / 0
Регистрация: 15.05.2015
Сообщений: 24

Кратчайший путь до определённой вершины графа - C++

05.06.2016, 20:03. Просмотров 85. Ответов 0
Метки (Все метки)

Добрый день! Дано такое задание по динамическому программированию - найти кратчайший путь от вершины А до вершины В (смотреть прикреплённую картинку, красным веделенны названия вершин, чёрным - вес).
Использую алгоритм Форда-Беллмана. В программе не используются ни векторы, ни списки.

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
void GraphType<Type>::bellman_ford(Type src){
    initDist();
    initPrev();
    dist[src] = 0;
 
    for(int i=1; i<numVertices-1; i++){
            for (int j = 0; j < numEdges; j++){
                    for(int from = 0; from<numVertices; from++){
                            for(int to = 0; to<numVertices; to++){
                                    if(dist[to]>edges[from][to]+dist[from]){
                                            dist[to]=edges[from][to]+dist[from];
                                            prev[to]=from;
               }
 
            }
 
        }
    }
    }
    printf("Vertex    Distance from Source\n");
    for (int i = 0; i < maxVertices; ++i)
        printf("%d \t\t %d\n", vertices[i], dist[i]);
 
}
Инициализация массивов расстояния и "предков"

C++
1
2
3
4
5
6
7
8
9
10
11
12
template<class Type>
void GraphType<Type>::initDist(){
    for (int i=0; i<maxVertices; i++){
        dist[i]= 10000000;
    }
}
template<class Type>
void GraphType<Type>::initPrev(){
    for (int i=0; i<maxVertices; i++){
        prev[i]=NULL;
    }
}
Что в функции Форда сделано не так? Все расстояния почему-то равны 0. Пользовалась данным алгоритмом https://en.wikipedia.org/wiki/Bellma...Ford_algorithm . И как потом восстановить путь, если мне нужны две конкретные вершины?
0
Миниатюры
Кратчайший путь до определённой вершины графа  
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru