Algoritmos de Caminho Mínimo - Dijkstra, Floyd, Bellman-Ford e Fluxo Máximo - Lista de Exercícios

1 Elabore um algoritmo que tenha por entrada um grafo G e escreva o caminho mínimo entre cada par de vértices em G Utilize o algoritmo de Dijkstra como função auxiliar deste algoritmo 2 Descreva a execução do algoritmo de Dijkstra e Floyd para encontrar o caminho mínimo entre os vértices 3 e 5 do seguinte grafo 3 Mostre o passo a passo do algoritmo de BellmanFord para determinar o peso entre A e todos os outros vértices 4 Implemente o algoritmo de Dijkstra 5 Implemente o algoritmo de Floyd 6 Implemente o algoritmo de BellmanFord 7 Mostre um digrafo ponderado sem ciclos negativos e um vértice inicial para qual o algoritmo de Dijkstra não retorna a resposta correta Mostre o passo a passo de execução do algoritmo até que se chegue ao erro 8 Responda de acordo com a rede e o fluxo a seguir a Qual o valor do fluxo da rede b Qual o corte com menor capacidade c Qual o corte com maior capacidade 9 Considere uma rede D definida pelos vértices V e arestas E de forma que 𝑐𝑒 1 𝑒 𝐸 a Qual a complexidade no pior caso da execução do Algoritmo FordFulkerson em D b Qual a complexidade no pior caso da execução do Algoritmo EdmondsKarp em D c 10 Qual a complexidade de melhor caso para o Algoritmo FordFulkerson Caracterize esses casos 11 Para cada subitem indique uma classe de grafos para a qual o Algoritmo FordFulkerson usando matriz de adjacência executa com a respectiva complexidade de tempo Considere que a forma com que um caminho de aumento é achado não é determinada ou seja a complexidade deve ser independente da forma com que a busca ser feita como uma DFS ou como uma BFS a θV2 b θV3 c θV3E 12 Considere uma rede D definida pelos vértices V e arestas E de forma fluxo máximo é Mostre que se multiplicarmos as 𝑓 capacidades de cada uma das arestas de D por o novo α fluxo máximo será 𝑓α 13 Seja D uma rede Prove que o seguinte procedimento não altera no fluxo máximo de D Se uv é a única aresta saindo de u remova o vértice u e adicione arestas wv para todo w tal que exista aresta wu com capacidade mincwu cuv 14 Crie um algoritmo que verifica uma resposta do algoritmo de Dijkstra em tempo Onm Para isso faça com que ele receba como entrada um grafo GVE um vértice v e dois vetores T e VCM com V posições cada um O seu algoritmo deve retornar VERDADEIRO ou FALSO correspondendo a duas verificações i T é um vetor cuja posição u possui a menor distância do vértice v até u e ii VCM é um vetor cuja posição u possui o vértice antecessor a u de um caminho mínimo entre v e u