0

Описание алгоритма

Не понимаю это: vector < vector < pair<int,int> > > g (n); Как мне считать таблицу смежности?

И не очень понимаю эти две строки:

vector<int> d (n, INF),  p (n); //INF - const int = 10000000;
vector<char> u (n);

pair<int,int>, где первый элемент пары — вершина, в которую ведёт ребро, а второй элемент — вес ребра.

Как можно обойтись без векторов, а простыми массивами?

1
  • А чем вам вектор не обычный массив? Разве что писать дольше, но зато и плюшек больше. Используйте псевдоним через using или typedef.
    – aleks.andr
    26 янв 2017 в 5:44

2 ответа 2

0

Удобнее всего заполнять соседей i-ых вершин через вектор, потому что массив может занимать больше памяти, чем вектор(массив создает лишние пустые элементы).

#include <vector>
#include <iostream>

using namespace std;

vector <vector < pair <int, int> > > v; // v[i] будет содержать всех соседей вершины i со своими ценами

int main()
{

    int n, m; // кол-во вершин у тебя в графе и кол-во дорог в графе соответсвенно
    int A, B, сost;

    cin >> n >> m;

    v.resize(n+1); // когда мы создали вектор он был пустым, после resize он стал состоять из n+1 пустых строк куда мы будем пихать наших соседей

    for(int i = 0; i < m; ++i){

          cin >> A >> B >> cost;
          v[a].push_back(make_pair(B, cost)); // помечаем что B сосед A c ценной cost
          v[b].push_back(make_pair(A, cost)); // помечаем что А сосед B с ценной cost

    }


}
0

Обычно для матрицы смежности используют

vector < vector <int> > a

И тогда скажем a[0] - вектор вершин в которые можно попасть из нулевой вершины. Но надо хранить еще вес и потому используют пару интов. Одно число - номер вершины, другое - вес ребра.

vector<int> d (n, INF)

изначально все кратчайшие пути = бесконечность(какое-то очень большое число)

p(n) это скорее всего массив предков, т.е p[i] = вершина j такая что кратчайший путь от начальной вершины до вершины i проходит через j, т.е 0 -> ... -> j -> i

1
  • 1
    А как мне считать матрицу смежности?
    – goodalien
    26 янв 2017 в 15:56

Ваш ответ

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

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