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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
dimsum
0 / 0 / 0
Регистрация: 15.05.2015
Сообщений: 24
#1

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

05.06.2016, 20:03. Просмотров 84. Ответов 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 . И как потом восстановить путь, если мне нужны две конкретные вершины?
Миниатюры
Кратчайший путь до определённой вершины графа  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.06.2016, 20:03
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Кратчайший путь до определённой вершины графа (C++):

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте! Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной...

Найти все вершины неориентированного графа, к которым существует путь заданной длины от выделенной его вершины - C++
Здравствуйте.Помогите пожалуйста решить задачу. Найти все вершины неориентированного графа, к которым существует путь заданной длины от...

Найти кратчайший путь из вершины u в вершину v - C++
Уффф, к завтрашнему дню нужно сдать эти задачи, помогите пожалуйста кто чем сможет :sorry: (следующие задачи через обходы в глубину и...

Найти все вершины графа, к которым существует путь заданной длины от вершины, номер которой вводится с клавиатуры. - C++
Помоги написать программу по графам плиз Найти все вершины графа, к которым существует путь заданной длины (не обязательно кратчайший)...

Кратчайший путь из одной вершины в другую с условием, что двигаться можно только прямо и вправо - C++
Условие Змей Горыныч оказался в лабиринте и хочет выбраться из него как можно скорее. К сожалению, после вчерашнего употребления кефира,...

Кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом - C++
Здравствуйте! Пишут, что можно находить кратчайший путь между вершинами взвешенного графа, в котором есть ребра с отрицательным весом. Как...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2016, 20:03
Привет! Вот еще темы с ответами:

Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А - C++
Найти все вершины графа, к которым от заданной вершины можно добраться по пути не длиннее А. Никаких наработок нет, к сожалению, вообще...

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

Кратчайший путь коня с++ - C++
помогите пожалуйста написать алгоритм кротчайшего пути коня на шахматной доске из А в Б

Графы кратчайший путь ! - C++
Помогите написать функцию для поиска кратчайшего пути между вершинами которые задаются с клавы я написал правда получилось что это...


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

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

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru