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

Работа с графами. Алгоритм Дейкстры - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 45, средняя оценка - 4.67
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
06.04.2013, 23:43     Работа с графами. Алгоритм Дейкстры #1
Может у кого есть исходник для реализации алгоритма Дейкстры, когда граф представлен не матрицей смежности, а списком рёбёр. Просто есть программа, где граф в виде матрицы смежности. А как изменить алгоритм не знаю. Или кто подскажет, как перейти от матрицы смежности к списку рёбер?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
06.04.2013, 23:43     Работа с графами. Алгоритм Дейкстры
Посмотрите здесь:

Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
Алгоритм Дейкстры C++
C++ Алгоритм Дейкстры
Алгоритм Дейкстры С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
07.04.2013, 03:55     Работа с графами. Алгоритм Дейкстры #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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
#include <map>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <limits>
#include <iterator>
#include <string>
#include <utility>
#include <iostream>
#include <bitset>
#include <numeric>
#include <iomanip>
#include <stack>
#include <set>
 
#ifdef ACMP_DEBUG
 
    #include <iostream>
    auto& in = std::cin;
    auto& out = std::cout;
 
#else
 
    #include <fstream>
    std::ifstream in("INPUT.TXT");
    std::ofstream out("OUTPUT.TXT");
 
#endif // ACMP_DEBUG
 
typedef std::size_t distance_t;
typedef std::size_t vertex_t;
 
std::pair<distance_t, vertex_t> my_make_pair
(
    const distance_t&   d,
    const vertex_t&     v
)
{
    return std::make_pair(d, v);
}
 
typedef std::set<std::pair<distance_t, vertex_t> > sorted_queue_t;
 
int main()
{
    static const distance_t INF = static_cast<distance_t>(-1);
 
    std::size_t m;
    vertex_t from, to;
    in >> m >> from >> to;
    --from;
    --to;
 
    // std::vector<std::vector<std::size_t> > g(m);
 
    typedef std::vector<std::vector<std::pair<distance_t, vertex_t> > > Graph_t;
    Graph_t g(m);
    for(std::size_t i = 0; i < m; ++i)
    {
        // g.at(i).resize(m);
        // for(std::size_t j = 0; j < g.at(i).size(); ++j)
        //     in >> g.at(i).at(j);
        for(std::size_t j = 0; j < m; ++j)
        {
            distance_t d;
            in >> d;
            if(d != static_cast<distance_t>(-1))
                g.at(i).push_back(my_make_pair(d, j));
        }
    }
 
    std::vector<distance_t> d(m, INF);
    d.at(from) = 0;
 
    sorted_queue_t q;
    q.insert(my_make_pair(d.at(from), from));
 
    while(!q.empty())
    {
        vertex_t v = q.begin() -> second;
        q.erase(q.begin());
 
        // for(vertex_t to_c = 0; to_c < g.at(v).size(); ++to_c)
        for
        (
            Graph_t::value_type::iterator it = g.at(v).begin();
            it != g.at(v).end();
            ++it
        )
        {
            vertex_t to_c = it -> second;
            // distance_t len = static_cast<distance_t>(g.at(v).at(to_c));
            distance_t len = it -> first;
            if(len == INF)
                continue;
            // std::cout << "Before if: v: " << v << ", to_c: " << to_c << std::endl;
            // std::cout << "d.at(v) + len: " << d.at(v) + len << std::endl;
            // std::cout << "d.at(to_c): " << d.at(to_c) << std::endl << std::endl;
            if(d.at(v) + len < d.at(to_c))
            {
                // std::cout << "v: " << v << ", to_c: " << to_c << std::endl;
                // std::cout << (d.at(v) + len) << " < " << d.at(to_c) << std::endl;
 
                q.erase(my_make_pair(d.at(to_c), to_c));
                d.at(to_c) = d.at(v) + len;
                q.insert(my_make_pair(d.at(to_c), to_c));
 
                // std::cout << "Is q empty? " << q.empty() << std::endl;
            }
        }
    }
 
    if(d.at(to) == INF)
        out << -1;
    else
        out << d.at(to);
    out << std::endl;
 
    return 0;
}
Задача
xtorne21st
интересующийся
300 / 271 / 19
Регистрация: 25.09.2010
Сообщений: 1,056
07.04.2013, 03:57     Работа с графами. Алгоритм Дейкстры #3
ссылка не рабочая
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
07.04.2013, 04:01     Работа с графами. Алгоритм Дейкстры #4
xtorne21st, насколько я помню, у acmp всегда были какие-то проблемы с сылками
Код
http://www.********/index.asp?main=task&id_task=132
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.04.2013, 08:08     Работа с графами. Алгоритм Дейкстры #5
существует два варианта алгоритма Дейкстры: для разряженных (небольшое количество ребер) и плотных (большое количество ребер) графов. вам который нужен?

Добавлено через 10 минут
soon, перепишите, пож, под консольный ввод. мне интересно, как быстро работает эта реализация...
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
07.04.2013, 08:32     Работа с графами. Алгоритм Дейкстры #6
salam, консольный ввод доступен, если задефайнить ACMP_DEBUG.
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.04.2013, 09:18     Работа с графами. Алгоритм Дейкстры #7
примерно то, что я и предполагал... может быть, вы мне объясните, зачем в таких задачах столько сложных медленных конструкций...?
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
07.04.2013, 10:01     Работа с графами. Алгоритм Дейкстры #8
salam, замена?
snw
10 / 10 / 0
Регистрация: 11.10.2012
Сообщений: 93
07.04.2013, 10:58     Работа с графами. Алгоритм Дейкстры #9
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 <fstream>
using namespace std;
ofstream out("output.txt");
int n = 100, Big = 10000, Color[101] = {0}, D[101], A[101][101], Way[101] = {0}, start, finish;
void Init()
{
    for(int i = 1; i <= 100; i++)
    {
        D[i] = Big;
        for(int j = 1; j <= 100; j++)
        {
            if(i == j)A[i][j] = 0;
            else A[i][j] = Big;
        }
    }
    int m;
    ifstream in("input.txt");
    in >> n >> m >> start >> finish;
    for(int i = 1; i <= m; i++)
    {
        int k, l;
        in >> k >> l;
        in >> A[k][l];
        A[l][k] = A[k][l];
    }
    in.close();
}
void Print(int V)
{
    if(V > 0)
    {
        Print(Way[V]);
        out << V << ' ';
    }
}
void dejkstra(int start)
{
    int i, j, m;
    D[0] = Big + 1;
    D[start] = 0;
    for(i = 1; i <= n; i++)
    {
        m = 0;
        for(j = 1; j <= n; j++)
        {
            if(D[j] < D[m] && Color[j] == 0)
            {
                m = j;
            }
        }
        Color[m] = 1;
        for(j = 1; j <= n; j++)
        {
            if(D[j] > A[m][j] + D[m])
            {
                D[j] = A[m][j] + D[m];
                Way[j] = m;
            }
        }
    }
}
int main()
{
    Init();
    dejkstra(start);
    out << D[finish] << endl;
    Print(finish);
    out.close();
}
input.txt:
4 4 1 4
1 2 6
1 3 2
2 3 3
2 4 5
barselona1994
0 / 0 / 0
Регистрация: 04.10.2012
Сообщений: 88
07.04.2013, 12:06  [ТС]     Работа с графами. Алгоритм Дейкстры #10
Цитата Сообщение от snw Посмотреть сообщение
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 <fstream>
using namespace std;
ofstream out("output.txt");
int n = 100, Big = 10000, Color[101] = {0}, D[101], A[101][101], Way[101] = {0}, start, finish;
void Init()
{
    for(int i = 1; i <= 100; i++)
    {
        D[i] = Big;
        for(int j = 1; j <= 100; j++)
        {
            if(i == j)A[i][j] = 0;
            else A[i][j] = Big;
        }
    }
    int m;
    ifstream in("input.txt");
    in >> n >> m >> start >> finish;
    for(int i = 1; i <= m; i++)
    {
        int k, l;
        in >> k >> l;
        in >> A[k][l];
        A[l][k] = A[k][l];
    }
    in.close();
}
void Print(int V)
{
    if(V > 0)
    {
        Print(Way[V]);
        out << V << ' ';
    }
}
void dejkstra(int start)
{
    int i, j, m;
    D[0] = Big + 1;
    D[start] = 0;
    for(i = 1; i <= n; i++)
    {
        m = 0;
        for(j = 1; j <= n; j++)
        {
            if(D[j] < D[m] && Color[j] == 0)
            {
                m = j;
            }
        }
        Color[m] = 1;
        for(j = 1; j <= n; j++)
        {
            if(D[j] > A[m][j] + D[m])
            {
                D[j] = A[m][j] + D[m];
                Way[j] = m;
            }
        }
    }
}
int main()
{
    Init();
    dejkstra(start);
    out << D[finish] << endl;
    Print(finish);
    out.close();
}
input.txt:
4 4 1 4
1 2 6
1 3 2
2 3 3
2 4 5
а какой граф вы представляете в своём input.txt....можно изображение?
Ternsip
 Аватар для Ternsip
660 / 188 / 6
Регистрация: 10.05.2012
Сообщений: 595
07.04.2013, 15:03     Работа с графами. Алгоритм Дейкстры #11
Для произвольного графа:
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
#include <iostream>
#include <cmath>
#include <vector>
#include <limits>
#include <algorithm>
 
using namespace std;
 
#define mp make_pair
 
int main(){         
    int n, m, v1, v2;
    cin >> n >> m >> v1 >> v2;
    v1--; v2--;
    vector<vector <pair<int, int>>> g(n);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;b--;
        g[a].push_back(mp(b, w));
        g[b].push_back(mp(a, w));
    }
    int INF = INT_MAX - 1e3;
    vector <int> d(n, INF);
    vector <bool> used(n, false);
    d[v1] = 0;
    int u = 0;
    while (u != -1){
        u = -1;
        int mx = INF;
        for (int i = 0; i < n; i++){
            if (!used[i] && d[i] < mx){
                mx = d[i];
                u = i;
            }
        }
        if (u != -1){
            for (int i = 0; i < g[u].size(); i++){
                int to = g[u][i].first;
                int w = g[u][i].second;
                if (!used[to] && d[u] + w < d[to]){
                    d[to] = d[u] + w;
                }
            }
            used[u] = 1;
        }
    }
    cout << ((d[v2] == INF)?-1:d[v2]);
    return 0;
}
Вот для разряженного за M Log N
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
#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>
#include <limits>
#include <queue>
#include <string>
#include <set>
#include <stack>
#include <tuple>
 
using namespace std;
 
#define mp make_pair
 
int main(){         
    freopen("input.txt", "rt", stdin);
    freopen("output.txt", "wt", stdout);
    int n, m;
    cin >> n >> m;
    vector<vector <pair<int, int>>> g(n);
    for (int i = 0; i < m; i++){
        int a, b, w;
        scanf("%d%d%d", &a, &b, &w);
        a--;b--;
        g[a].push_back(mp(b, w));
        g[b].push_back(mp(a, w));
    }
    int INF = INT_MAX - 1e3;
    vector <int> d(n, INF), p(n, -1);
    vector <bool> used(n, false);
    set <pair<int, int>> mn; 
    d[0] = 0;
    mn.insert(mp(0, 0));
 
    while (!mn.empty()){
        int u = (*mn.begin()).second;
        mn.erase(mn.begin());
        for (int i = 0; i < g[u].size(); i++){
            int to = g[u][i].first;
            int w = g[u][i].second;
            if (!used[to] && d[u] + w < d[to]){
                d[to] = d[u] + w;
                p[to] = u;
                mn.insert(mp(d[to], to));
            }
        }
    }
    if (d[n-1] == INF){
        cout << "No solution";
    }else{
        stack <int> st;
        int t = n-1;
        while (t != 0){
            st.push(t+1);
            t = p[t];
        }
        printf("%d ", 1);
        while (!st.empty()){
            printf("%d ", st.top());
            st.pop();
        }
    }
    return 0;
}
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.04.2013, 16:51     Работа с графами. Алгоритм Дейкстры #12
soon, я имел в виду весь ваш код...
soon
 Аватар для soon
2536 / 1301 / 81
Регистрация: 09.05.2011
Сообщений: 3,086
Записей в блоге: 1
07.04.2013, 17:03     Работа с графами. Алгоритм Дейкстры #13
salam, таки, весь? scanf вместо cin, статические массивы вместо векторов, ага?
salam
157 / 138 / 11
Регистрация: 10.07.2012
Сообщений: 709
07.04.2013, 17:07     Работа с графами. Алгоритм Дейкстры #14
я тоже пишу с векторами, но без особых премудростей получается в два раза быстрее...
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
07.04.2013, 17:46     Работа с графами. Алгоритм Дейкстры
Еще ссылки по теме:

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

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

Или воспользуйтесь поиском по форуму:
snw
10 / 10 / 0
Регистрация: 11.10.2012
Сообщений: 93
07.04.2013, 17:46     Работа с графами. Алгоритм Дейкстры #15
4 4 1 4 - 4 вершины, 4 ребра, с 1 по 4 вершину делаем обход
1 2 6 - 1 и 2 номера вершин, 6 расстояние.
1 3 2
2 3 3
2 4 5
Yandex
Объявления
07.04.2013, 17:46     Работа с графами. Алгоритм Дейкстры
Ответ Создать тему
Опции темы

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