Количество кратчайших путей

247
29 апреля 2018, 21:43
Как можно модифицировать код для поиска количества кратчайших путей?

Сейчас: Код ищет количество точек, через которое пройдёт алгоритм для возвращения в исходную позицию

Пометки: граф невзвешенный, ориентированный.

 #include <iostream>
    #include <vector>
    #include <queue>
    using namespace std;

    int main()
    {
          int start;
            int n;
            cin >> n;  // число вершин 
              cin  >> start;
           vector <vector <int> > g (n, vector<int>(n, 0));    //матрица смежности
            for (int i = 0; i < n; i++)
                    for (int j = 0; j < n; j++)
                            cin >> g[i][j];

            int finish;
           finish=start;
            vector <int>  d(n, -1);  // массив длин (хранит длину до данной вершины)
            d[start-1] = 0;
            queue <int> q;   // создание очереди  из вершин
            q.push(start-1);  // добавление в очередь точки старта 
           vector <bool> used(n,false);    // буловский массив посещений (true если данная вершина была обработана и false если вершина не обработана) 
           used[start] = true;   // помечаем стартовую вершину, что ее уже посетили
            while (!q.empty())
            {
            int v = q.front();
                q.pop();
            for (int i = 0; i < n; ++i)
            {
                int to = g[v][i];
                if (!used[i] && (to == 1))
                {
                    used[i] = true;
                    q.push(i);
                    d[i] = d[v] + 1;
    }
            }  
             }
           cout << d[finish-1];
            return 0;
    }      
Answer 1

Можно взять матрицу смежности, и возводить её во вторую, третью и т.д. степень, пока диагональные элементы A[i,i] не станут ненулевыми.

Формулировка неясная, и пока нельзя понять, нужно ли искать количество циклов для каждой вершины, минимальные циклы для одной выбранной вершины или ещё что.

В любом случае диагональный элемент A[i,i] в матрице Ak даёт количество циклов длины k для данной вершины.

Для примера из ссылки куб матрицы показывает, что циклы длиной 3 есть для вершин 3,4,5, а четвертая степень - циклы длиной 4 для вершин 2,3,4,5. В данном примере всех циклов по одному, а вот путей 4-6 длиной три - две штуки

        X1  X2  X3  X4  X5  X6
    X1  0   0   0   1   0   1
    X2  0   0   1   0   0   0
A3= X3  0   0   1   1   0   1
    X4  0   0   0   1   1   2
    X5  0   1   0   0   1   1
    X6  0   0   0   0   0   0
        X1  X2  X3  X4  X5  X6
    X1  0   0   1   0   0   0
    X2  0   1   0   0   1   1
A4= X3  0   1   1   0   1   1
    X4  0   0   1   1   0   1
    X5  0   0   0   1   1   2
    X6  0   0   0   0   0   0
Answer 2

Если мы знаем расстояние, то есть длину кратчайшего пути между вершинами i, j, и оно равно d, то достаточно рассмотреть d-ую степень матрицы смежности графа. Элемент с координатами (i,j) матрицы A^d покажет число путей длины d от i до j; все они являются кратчайшими.

READ ALSO
Удаление элементов из очереди

Удаление элементов из очереди

Имеется часть кода:

253
Найти k1-количество одинаковых элементов в двумерном массиве c++; [требует правки]

Найти k1-количество одинаковых элементов в двумерном массиве c++; [требует правки]

Найти k1-количество одинаковых элементов в двумерном массиве c++;

214
Почему не работают мои запросы sql в qt

Почему не работают мои запросы sql в qt

Вот обычный код подклк бд, простой запрос

204