Fluxo Máximo em Grafos - Implementações em Python de Caminho Aumentante e Ford-Fulkerson

15caminhoAumentantepy Descrição Faça um programa que leia um grafo ponderado e calcule um caminho aumentante de um vértice s até um vértice t usando uma busca em largura BFS Entrada Recebe n m s e t n é o total de vértices m o total de arcos s é a fonte e t é o sumidouro A seguir m linhas cada linha com um trio de inteiros correspondentes ao início e fim do arco seguido do peso do arco Os vértices são identificados de 0 até n1 Saída Imprime um caminho aumentante e a capacidade deste caminho O formato do caminho é i j peso Exemplo Entrada 6 9 0 5 0 1 16 0 2 13 1 3 12 2 1 4 2 4 14 3 2 9 3 5 20 4 3 7 4 5 4 Saída 0 1 16 1 3 12 3 5 20 12 16aumentaFluxopy Descrição Faça um programa que leia um grafo ponderado e dois vértices s e t Calcule o primeiro caminho aumentante de um vértice s até um vértice t usando uma busca em largura BFS Calcule o resultado do primeiro aumento de fluxo usando o caminho aumentante encontrado Considere o fluxo inicial zero Entrada Recebe n m s e t n é o total de vértices m o total de arcos s é a fonte e t é o sumidouro A seguir m linhas cada linha com um trio de inteiros correspondentes ao início e fim do arco seguido do peso do arco Os vértices são identificados de 0 até n1 Saída Linha 1 imprima o caminho aumentante O formato do caminho é i j peso Linha 2 imprima a capacidade deste caminho Imprima também o resultado de aumentar o fluxo com este caminho aumentante Linha 3 imprima a matriz de fluxo Linha 4 imprima a matriz de adjacência da rede residual resultante após o aumento do fluxo Exemplo Entrada 6 9 0 5 0 1 16 0 2 13 1 3 12 2 1 4 2 4 14 3 2 9 3 5 20 4 3 7 4 5 4 Saída 0 1 16 1 3 12 3 5 20 12 0 12 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 12 0 0 0 0 0 0 0 0 0 0 0 0 0 4 13 0 0 0 12 0 0 0 0 0 0 4 0 0 14 0 0 12 9 0 0 8 0 0 0 7 0 4 0 0 0 12 0 0 17fordFulkersonpy Descrição Faça um programa que leia um grafo ponderado e calcule o fluxo máximo de um vértice s até um vértice t pelo algoritmo de FordFulkerson Entrada Recebe n m s e t n é o total de vértices m o total de arcos s é a fonte e t é o sumidouro A seguir m linhas cada linha com um trio de inteiros correspondentes ao início e fim do arco seguido do peso do arco Os vértices são identificados de 0 até n1 Saída Imprime a matriz de fluxo e a matriz de adjacência da rede residual obtidas pelo algoritmo de FordFulkerson Exemplo Entrada 6 9 0 5 0 1 16 0 2 13 1 3 12 2 1 4 2 4 14 3 2 9 3 5 20 4 3 7 4 5 4 Saída 0 12 11 0 0 0 0 0 0 12 0 0 0 0 0 0 11 0 0 0 0 0 0 19 0 0 0 7 0 4 0 0 0 0 0 0 0 4 2 0 0 0 12 0 0 0 0 0 11 4 0 0 3 0 0 12 9 0 7 1 0 0 11 0 0 0 0 0 0 19 4 0