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

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

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 20, средняя оценка - 4.75
АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
#1

Алгоритм Дейкстра - C++

11.12.2010, 18:10. Просмотров 2468. Ответов 4
Метки нет (Все метки)

Помогите, люди добрые, пожалуйста с реализацией алгоритма Дейкстра, мож где есть хорошее объяснение али код какой, причем надо реализовать его с использованием связных списков и очереди с приоритетом..
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
11.12.2010, 18:10
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Алгоритм Дейкстра (C++):

Алгоритм Дейкстра - C++
Есть у кого исходник кода,чтобы проверяло достижимость из выбранного города во все остальные? или помогите, пожалуйста, выделить вот...

АЛГОРИТМ ДЕЙКСТРА - C++
Доброго времени суток всем! У меня вопрос. Написала программку для нахождения кратчайшего пути (алгоритм Дейкстра), но мне надо её как то...

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

Матрица Форда Беллмана и метод Дейкстра - C++
Тут такая проблема , задали написать матрицу с помощью єтих методов/ вопрос : Как вставить сюда матрицу (тоесть с помощью методов Беллмана...

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

Волновой алгоритм поиска (Алгоритм A* / Алгоритм А стар) - C++
Хочу разработать алгоритм для решения головоломки с подвижными дисками (перестановочная головоломка). Определение. Перестано́вочные...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
11.12.2010, 20:06 #2
На вики есть:
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <iostream>
#include <set>
#include <vector>
using namespace std;
 
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
 
const int MAX = 1001;
const int MAXINT = 1000000000;
 
int n;
vvii G(MAX);
vi D(MAX, MAXINT);
 
void Dijkstra(int s)
{
    set<ii> Q;
    D[s] = 0;
    Q.insert(ii(0,s));
 
    while(!Q.empty())
    {
        ii top = *Q.begin();
        Q.erase(Q.begin());
        int v = top.second;
        int d = top.first;
 
        for (vii::const_iterator it = G[v].begin(); it != G[v].end(); it++)
        {
            int v2 = it->first;
            int cost = it->second;
            if (D[v2] > D[v] + cost)
            {
                if (D[v2] != 1000000000)
                {
                    Q.erase(Q.find(ii(D[v2], v2)));
                }
                D[v2] = D[v] + cost;
                Q.insert(ii(D[v2], v2));
            }
        }
    }
}
 
int main()
{
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
 
    int m, s, t = 0;
    scanf("%d %d %d %d", &n, &m, &s, &t);
 
    for (int i = 0; i < m; i++)
    {
        int a, b, w = 0;
        scanf("%d %d %d", &a, &b, &w);
        G[a - 1].push_back(ii(b - 1, w));
        G[b - 1].push_back(ii(a - 1, w));
    }
 
    Dijkstra(s - 1);
 
    printf("%d\n", D[t - 1]);
 
    return 0;
}
0
АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
11.12.2010, 20:47  [ТС] #3
дружище, очень благодарю тебя, а ты бы ссылку не дал бы на вики(я че то не нашел...)? там наверняка что - то нибудь написано по этому поводу я бы почитал, по-понимал заодно)
заранее спасибо!)
0
st_dent
64 / 64 / 3
Регистрация: 05.07.2010
Сообщений: 219
11.12.2010, 21:00 #4
АлександрШ, тут
0
АлександрШ
2 / 2 / 0
Регистрация: 11.12.2010
Сообщений: 16
11.12.2010, 22:04  [ТС] #5
много тут написато)) ладно, разберусь, еще раз спасибо за код)
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
11.12.2010, 22:04
Привет! Вот еще темы с ответами:

Помогите алгоритм для char переделать в алгоритм для float - C++
char* DecToBin(char x, char* str) { int i; for (i = sizeof(x)*8-1; i&gt;=0; i--) { str = (x&amp;1 == 1) ? '1' : '0'; x = x &gt;&gt;...

Волновой алгоритм (алгоритм Ли) - C++
Здравствуйте! У кого-нибудь есть реализованный волновой алгоритм (алгоритм Ли) ? Дело в том, что я игрушку захотел написать (что-то...

Алгоритм дейкстра - C#
Нужно запрограммировать алгоритм Дейкстра. Не понимаю как можно дальше найти путь в массиве для решения задачи. Вот мой код: using...

Алгоритм Дейкстра - Delphi
Здравствуйте! Помогите пожалуйста!! У меня в программе есть такое: //Вывод результата ListBox1.Clear; for i := 1 to n do ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
11.12.2010, 22:04
Ответ Создать тему
Опции темы

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