1

Нужна помощь с написанием программы на С++, а именно алгоритма Габова нахождения кратчайших путей с помощью масштабирования. Вся сложность в том, что на русском языке информации про этот алгоритм очень мало(Кормен, Алгоритмы: построение и анализ, изд.3, с 718 - единственное упоминание). Пробовал искать на англоязычных сайтах, нашёл псевдокод, но с реализацией проблема.Ссылка на сайт с псевдокодом - https://pdfs.semanticscholar.org/b4db/ebb43dbe4fd261a32f80f86f2f98b246a2eb.pdf

Вот мой нерабочий код, сделанный с псевдокода:

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
#include <vector>
#include<functional>
#include <fstream>
using namespace std;

int n;
int maxW(int** g)
{
    int max = g[0][0];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (g[i][j] > max)
            {
                max = g[i][j];
            }
        }
    }
    return max;
}
void Gabow(int s, int** G)
{
    vector <int> dist(n,INT_MAX);
    int w = log2(maxW(G));
    priority_queue <int, vector <int>, greater <int> > q;
    dist[s] = 0;
    q.push(dist[s]);
    while (!q.empty())
    {
        int u = q.top();
        q.pop();
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                if (G[i][j] != 0)
                {
                    int wi = G[i][j] >> w;
                    if (dist[j] > u + wi)
                    {
                        dist[j] = u + wi;
                        q.push(dist[j]);
                    }
                }
            }
        }
    }
    while (w > 0)
    {
        w--;
        vector <int> extradist(n, INT_MAX);
        extradist[s] = 0;
        priority_queue <pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
        q.push(make_pair(extradist[s],dist[s]));
        while (!q.empty())
        {
            pair<int,int> u = q.top();
            q.pop();
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (G[i][j] != 0)
                    {
                        int wi = G[i][j] >> w;
                        int l = wi + 2 * (u.second - dist[j]);
                        if (extradist[j] > u.first + l)
                        {
                            extradist[j] = u.first + l;
                            q.push(make_pair(extradist[j],dist[j]));
                        }
                    }
                }
            }
        }
        for (int i = 0; i < n; i++)
        {
            if (dist[i] < INT_MAX)
            {
                dist[i] = 2 * dist[i] + extradist[i];
            }
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << dist[i] << " ";
    }
}
int main()
{
    ifstream infile("graph.txt");
    infile >> n;
    int** mas = new int*[n];
    for (int i = 0; i < n; i++)
    {
        mas[i] = new int[n];
    }
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            infile >> mas[i][j];
        }
    }
    int start = 0;
    Gabow(start,mas);
    infile.close();
    for (int i = 0; i < n; i++)
    {
        delete[]mas[i];
    }
    delete[]mas;
    return 0;
}

Пример входных данных (матрица смежности):

4
0 2 0 0
0 0 1 9
6 0 0 3 
0 0 0 0

Вывод алгоритма: 0 2 1 3
Правильный вывод: 0 3 4 7

13
  • Так а в чем с реализацией проблема? 9 янв 2020 в 20:03
  • Сижу уже два дня с ним, никак не могу реализовать. Абсолютно не понимаю. 9 янв 2020 в 20:13
  • Так а ваши попытки где? Где именно затык? Пока это звучит просто как "сделайте за меня" 9 янв 2020 в 20:21
  • сейчас выложу свой нерабочий код 9 янв 2020 в 20:22
  • Так и в чем вопрос? Что конкретно не работает, что вы в вашем коде делаете? 9 янв 2020 в 20:30

1 ответ 1

2

Если аккуратно переписать псевдокод из вышеупомянутой статьи на С++, то получится нечто такое:

#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream>
#include <cmath>
#include <limits>
#include <vector>
#include <functional>
#include <fstream>

using namespace std;

typedef unsigned vertex_t;
typedef unsigned dist_t;

size_t n;
int maxW(dist_t** g)
{
    dist_t max = g[0][0];
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            if (g[i][j] > max)
            {
                max = g[i][j];
            }
        }
    }
    return max;
}

struct VertexPrio {
    vertex_t v;
    dist_t prio;

    bool operator<(const VertexPrio& other) const {
        return this->prio < other.prio;
    }
    bool operator>(const VertexPrio& other) const {
        return this->prio > other.prio;
    }
};

void Gabow(vertex_t s, dist_t** G) {
    vector <dist_t> dist(n,std::numeric_limits<dist_t>::max());
    unsigned i = log2(maxW(G));
    priority_queue <VertexPrio, std::vector<VertexPrio>, std::greater<VertexPrio>> q;
    dist[s] = 0;
    q.push(VertexPrio{s,0});

    while (!q.empty()) {
        vertex_t u = q.top().v;
        q.pop();

        for (vertex_t v = 0; v < n; v++) {
            if (G[u][v] != 0) {
                unsigned wi = G[u][v] >> i;
                if (dist[v] > dist[u] + wi) {
                    dist[v] = dist[u] + wi;
                    q.push(VertexPrio{v,dist[v]});
                }
            }
        }
    }

    while (i > 0)
    {
        i--;
        vector <dist_t> extradist(n, std::numeric_limits<dist_t>::max());
        extradist[s] = 0;
        priority_queue <VertexPrio, std::vector<VertexPrio>, std::greater<VertexPrio>> q;
        q.push(VertexPrio{s,0});
        while (!q.empty()) {
            vertex_t u = q.top().v;
            q.pop();

            for (vertex_t v = 0; v < n; v++) {
                if (G[u][v] != 0) {
                    unsigned wi = G[u][v] >> i;
                    int l = wi + 2 * (dist[u] - dist[v]);
                    if (extradist[v] > extradist[u] + l) {
                        extradist[v] = extradist[u] + l;
                        q.push(VertexPrio{v, extradist[v]});
                    }
                }
            }
        }
        for (vertex_t u = 0; u < n; u++) {
            if (dist[u] < std::numeric_limits<dist_t>::max()) {
                dist[u] = 2 * dist[u] + extradist[u];
            }
        }
    }

    for (vertex_t v = 0; v < n; v++) {
        cout << dist[v] << " ";
    }
    cout << std::endl;
}
int main()
{
    ifstream infile("graph.txt");
    infile >> n;
    dist_t** mas = new dist_t*[n];

    for (size_t i = 0; i < n; i++)
    {
        mas[i] = new dist_t[n];
    }
    for (size_t i = 0; i < n; i++)
    {
        for (size_t j = 0; j < n; j++)
        {
            infile >> mas[i][j];
        }
    }
    infile.close();

    Gabow(/*start=*/ 0,mas);

    for (size_t i = 0; i < n; i++)
    {
        delete[]mas[i];
    }
    delete[]mas;
    return 0;
}

Правильный вывод: 0 3 4 7

На самом деле правильный ответ: 0 2 3 6

1
  • Да, с ответом я действительно ошибся) Все отлично работает, спасибо! 10 янв 2020 в 10:18

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.