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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 15, средняя оценка - 4.67
Аня6
1 / 1 / 0
Регистрация: 23.10.2011
Сообщений: 21
#1

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

06.06.2012, 14:02. Просмотров 1790. Ответов 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
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;
            }
        }
    }
}
Буду очень благодарна за помощь!!! Прям очень-очень нужно....
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.06.2012, 14:02
Здравствуйте! Я подобрал для вас темы с ответами на вопрос помогите реализовать алгоритм Дейкстры - алгоритм поиска кратчайшего пути (C++):

Построить алгоритм поиска кратчайшего пути между двумя вершинами в графе - C++
Блин я уже так задолбался с этим заданием может кто нибудь поможет: Построить алгоритм поиска кратчайшего пути между двумя...

Нужен алгоритм поиска пути в этом лабиринте (будь то волновой алгоритм или алгоритм правой/левой руки ) - C++
#include &quot;stdafx.h&quot; #include &lt;iostream&gt; #include &lt;conio.h&gt; using namespace std; void lab () { int s1 = 0; int s2 =...

Вывод пути (алгоритм Дейкстры) - C++
Реализация алгоритма Дейкстра. В массиве distance - найденные кратчайшие пути, visited - логический, для хранения информации о...

Нахождение кратчайшего пути в графе, алгоритм Уоршелла - C++
Привет всем! алгоритм уоршелла, нужно найти кратчайший путь в графе. ввожу матрицу 0 1 5 1 0 2 5 2 0 работает нормально, все...

Алгоритм Дейкстра. Поиск кратчайшего пути с запоминанием маршрута - C++
Всем привет, есть алгоритм Дейкстра, который находит минимальный маршрут из главной вершины во все остальные. Как сделать, чтобы помимо...

Требуется реализовать алгоритм Дейкстры начинающему программисту - C++
Ребята огромная просьба помочь с программой. Условия следушие-реализовать алгоритм Дейкстры на С++. Я сидел парился и смог только часть...

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

Определение кратчайшего пути алгоритмом Дейкстры - C++
Разработка программного комплекса для определения кратчайшего пути алгоритмом Дэйстри. Программный комплекс решает задачу поиска самого...

Алгоритм поиска пути - C++
Ребята, помогите разобраться с кодом. Пробую реализовать преследование привидений пакмана. При этом использую алгоритм поиска пути и...

Волновой алгоритм поиска пути - C++
Добрый день. Реализую всем известный алгоритм поиска кратчайшего пути. Но не могу понять одну вещь. Пройдя волновым методам по...

Алгоритм поиска пути и прорисовка его - C++
Есть класс Карта #ifndef MAP_H #define MAP_H #include &lt;SFML\Graphics.hpp&gt; class Map{ private: int m_level; public:


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

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

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