1

Edmonds-Karp アルゴリズムを C++ で実装しました。小さなグラフでテストしようとしたところ、終了しませんでしたが、スタックした場所を特定できませんでした。私は通常cout、無限に印刷される場所が見つかるまで何かを使用しますが、ここでは作業しませんでした. プログラムは何も印刷しません。プログラムの最初の行に a を入れようとしましたが、出力coutされません。何も出力しない理由や、無限ループを特定する方法についてのヒントがある理由を誰でも知っていますか?

誰かが見たい場合のコードは次のとおりです。

int main ()
{
FILE *graph_file;
graph_file = fopen("grafo.txt", "r");
if (graph_file == NULL)
{
    cout << "Não foi possível abrir o arquivo 'grafo.txt'" << endl;
    exit(1);
}

char line[MAX_LINE];
char *line_split = NULL;

// pegar informações do grafo para armazenar o tamanho adequado dos vetores
fgets(line, MAX_LINE, graph_file);
while (feof(graph_file) == 0)
{
    if (line[0] == 'a') // é uma aresta
    {
        line_split = strtok(line, " "); // a

        line_split = strtok(NULL, " "); // vertice origem da aresta
        int origin = atoi(line_split);

        line_split = strtok(NULL, " "); // vertice destino da aresta
        int destiny = atoi(line_split);

        line_split = strtok(NULL, " "); // peso da atesta
        int capacity = atoi(line_split);

        insert_edge(origin, destiny, capacity);
    }
        fgets(line, MAX_LINE, graph_file);
}

//print_graph();

int origin = 1;
int destiny = 6;

calc_valid_path(origin, destiny);

while (precursor[destiny] != 0)
{
    int max_cap = get_path_max_cap(origin, destiny);

    int i = destiny;
    while (i != origin)
    {
        Edge *temp = get_edge(precursor[i], i);
        temp->flow = temp->flow + max_cap;

        temp = get_edge(i, precursor[i]);
        if (temp == NULL) // se a aresta inversa ainda não existe, cria
        {
            insert_edge (i, precursor[i], 0);
            temp = get_edge(i, precursor[i]);
        }
        temp->flow = temp->flow - max_cap;
        i = precursor[i];
    }

    calc_valid_path(origin, destiny);
}

cout << "Flow: " << get_flow(destiny);

return 0;
}
4

1 に答える 1