Как можно модифицировать код для поиска количества кратчайших путей?
Сейчас: Код ищет количество точек, через которое пройдёт алгоритм для возвращения в исходную позицию
Пометки: граф невзвешенный, ориентированный.
#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;
}