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

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

Восстановить пароль Регистрация
 
dimsum
0 / 0 / 0
Регистрация: 15.05.2015
Сообщений: 24
05.06.2016, 20:03     Кратчайший путь до определённой вершины графа #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
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 . И как потом восстановить путь, если мне нужны две конкретные вершины?
Миниатюры
Кратчайший путь до определённой вершины графа  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 20:03     Кратчайший путь до определённой вершины графа
Посмотрите здесь:

Кратчайший путь в графе. C++
Кратчайший путь в графе(Рекурсия) C++
Кратчайший путь коня с++ C++
C++ Графы кратчайший путь !
Найдите кратчайший путь в графе C++
Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом C++
C++ Найти кратчайший путь из вершины u в вершину v
Как найти кратчайший путь в лабиринте? C++

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

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

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