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

помогите реализовать алгоритм Дейкстры - алгоритм поиска кратчайшего пути - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Аня6
1 / 1 / 0
Регистрация: 23.10.2011
Сообщений: 21
06.06.2012, 14:02     помогите реализовать алгоритм Дейкстры - алгоритм поиска кратчайшего пути #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
25
26
27
28
29
30
31
const int INF = 1000000000;
 
int main() {
    int n;
    ... чтение n ...
    vector < vector < pair<int,int> > > g (n);
    ... чтение графа ...
    int s = ...; // стартовая вершина
 
    vector<int> d (n, INF),  p (n);
    d[s] = 0;
    vector<char> u (n);
    for (int i=0; i<n; ++i) {
        int v = -1;
        for (int j=0; j<n; ++j)
            if (!u[j] && (v == -1 || d[j] < d[v]))
                v = j;
        if (d[v] == INF)
            break;
        u[v] = true;
 
        for (size_t j=0; j<g[v].size(); ++j) {
            int to = g[v][j].first,
                len = g[v][j].second;
            if (d[v] + len < d[to]) {
                d[to] = d[v] + len;
                p[to] = v;
            }
        }
    }
}
Буду очень благодарна за помощь!!! Прям очень-очень нужно....
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2012, 14:02     помогите реализовать алгоритм Дейкстры - алгоритм поиска кратчайшего пути
Посмотрите здесь:

Реализовать алгоритм бинарного поиска с рекурсией C++
C++ Требуется реализовать алгоритм Дейкстры начинающему программисту
помогите, неправильно выводит путь алгоритм Дейкстры C++
C++ Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе
Волновой алгоритм поиска пути C++
Нахождение кратчайшего пути в графе, алгоритм Уоршелла C++
C++ Вывод пути (алгоритм Дейкстры)
C++ Алгоритм поиска пути в лабиринте, заданном связным графом

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

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

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