Вероятность для каждой вершины

У меня есть граф с N вершинами и M ребрами (N между 1 и 15 и M между 1 и N ^ 2). График направлен и взвешен (с вероятностью для этого точного ребра). Вам дается начальная вершина и количество ребер. Затем программа рассчитает вероятность для каждой вершины, являющейся конечной вершиной.

Ввод экзамена:

3 3 // Количество вершин и количество ребер

1 2 0,4 // Кромка № 1 от вершины 1 до 2 с вероятностью 0,4

1 3 0,5 // Кромка № 2 от вершины 1 до 3 с вероятностью 0,5

2 1 0,8 // Edge nr.3 …

3 // Количество вопросов

2 1 // Начальная вершина, количество ребер для посещения

1 1

1 2

Выход:

0,8 0,2 0,0 // Вероятность для вершины 1 beign последней вершины равна 0,8, для вершины 2 — 0,2, а для вершины 3 — 0,0

0,1 0,4 0,5

0,33 0,12 0,55

Я использовал DFS в моем решении, но когда количество ребер для посещения может быть до 1 миллиарда, это слишком медленно … Я смотрел на DP, но я не уверен, как реализовать это для этой конкретной проблемы (если это даже правильный способ ее решения). Поэтому я надеялся, что некоторые из вас могут предложить альтернативу DFS и / или, возможно, способ использования / реализации DP.

(Я знаю, что это может быть немного грязно, я программирую на C ++ только месяц)

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

struct bird {
int colour;
float probability;
};

struct path {
int from;
int to;
};

vector <vector <bird>> birdChanges;
vector <int> layer;
vector <double> savedAnswers;
stack <path> nextBirds;
int fromBird;

//Self loop
void selfLoop(){
float totalOut = 0;
for (int i = 0; i < birdChanges.size(); i++) {
for (int j = 0; j < birdChanges[i].size(); j++) {
totalOut += birdChanges[i][j].probability;
}
if (totalOut < 1) {
bird a;
a.colour = i;
a.probability = 1 - totalOut;
birdChanges[i].push_back(a);
}
totalOut = 0;
}
}

double fillingUp(double momentarilyProbability, long long int numberOfBerries){
int layernumber=0;
while (layer[numberOfBerries - (1+layernumber)] == 0) {
layernumber++;
if (numberOfBerries == layernumber) {
break;
}
}
layernumber = layer.size() - layernumber;
path direction;
int b;
if (layernumber != 0) {
b= birdChanges[nextBirds.top().from][nextBirds.top().to].colour;//Usikker
}
else {
b = fromBird;
}
while (layer[numberOfBerries - 1] == 0) {
//int a = birdChanges[nextBirds.top().from][nextBirds.top().to].colour;
if (layernumber != 0) {
momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability;
//b = birdChanges[nextBirds.top().from][nextBirds.top().to].colour;
}
for (int i = 0; i < birdChanges[b].size(); i++) {
direction.from = b;
direction.to = i;
//cout << endl << "Stacking " << b << " " << birdChanges[b][i].colour;
nextBirds.push(direction);
layer[layernumber]++;
}
layernumber++;
b = birdChanges[nextBirds.top().from][nextBirds.top().to].colour;
}
//cout << "Returning" << endl;
return momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability;;
}

//DFS
void depthFirstSearch(int fromBird, long long int numberOfBerries) {
//Stack for next birds (stack)
path a;
double momentarilyProbability = 1;//Momentarily probability (float)
momentarilyProbability=fillingUp(1, numberOfBerries);
//cout << "Back " << momentarilyProbability << endl;
//Previous probabilities (stack)
while (layer[0] != 0) {
//cout << "Entering" << endl;
while (layer[numberOfBerries - 1] != 0) {
savedAnswers[birdChanges[nextBirds.top().from][nextBirds.top().to].colour] += momentarilyProbability;
//cout << "Probability for " << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << " is " << momentarilyProbability << endl;
momentarilyProbability = momentarilyProbability / birdChanges[nextBirds.top().from][nextBirds.top().to].probability;
nextBirds.pop();
layer[numberOfBerries - 1]--;
if (layer[numberOfBerries - 1] != 0) {
momentarilyProbability *= birdChanges[nextBirds.top().from][nextBirds.top().to].probability;
}
}

if (layer[0] != 0) {
int k = 1;
while (layer[layer.size() - k]==0&&k+1<=layer.size()) {
//cout << "start" << endl;
momentarilyProbability = momentarilyProbability / birdChanges[nextBirds.top().from][nextBirds.top().to].probability;
//cout << "Popping " << nextBirds.top().from << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << endl;
nextBirds.pop();
//cout << "k " << k << endl;
layer[numberOfBerries - 1 - k]--;
k++;
//cout << "end" << endl;
}
}
if (layer[0] != 0) {
//cout << 1 << endl;
//cout << "Filling up from " << nextBirds.top().from << birdChanges[nextBirds.top().from][nextBirds.top().to].colour << endl;
momentarilyProbability = fillingUp(momentarilyProbability, numberOfBerries);
}
}
//Printing out
for (int i = 1; i < savedAnswers.size(); i++) {
cout << savedAnswers[i] << " ";
}
cout << endl;
}

int main() {
int numberOfColours;
int possibleColourchanges;
cin >> numberOfColours >> possibleColourchanges;
birdChanges.resize(numberOfColours+1);
int from, to;
float probability;
for (int i = 0; i < possibleColourchanges; i++) {
cin >> from >> to >> probability;
bird a;
a.colour = to;
a.probability = probability;
birdChanges[from].push_back(a);
}
selfLoop();
int numberOfQuestions;
cin >> numberOfQuestions;
long long int numberOfBerries;
for (int i = 0; i < numberOfQuestions; i++) {
cin >> fromBird >> numberOfBerries;
savedAnswers.assign(numberOfColours + 1, 0);
layer.resize(numberOfBerries, 0);
//DFS
depthFirstSearch(fromBird, numberOfBerries);
}
system("pause");
}