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

У меня есть граф с 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 // Номер кромки 3 ...

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

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

1 1

1 2

Вывод:

0,8 0,2 0,0 // Вероятность того, что вершина 1 окажется последней, равна 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");
}