Professor,
A minha pergunta é em relação à 3a questão. Porque fiz uma função O(A).
Se o digrafo não tem arcos com custo negativo, então o menor caminho será o menor custo de 1 arco pertencente ao corte (S ,T). Em particular se S e T não são disjuntos, o custo é 0. Então basta percorrer cada arco do uma única vez e ver se ele pertence ao corte e se o custo é menor que o já encontrado.
Qualquer caminho mínimo que tenha mais de um arco, tem um arco que pertence ao corte e esse arco é um caminho de custo mínimo.
Daí o problema ser muito mais simples e não precisar de Dijkstra nem de heap.
Não sei se entendi errado a questão ou está mal formulada. Se esse não é o caso, favor fornecer contra-exemplo.
Pelo que eu entendi da questão, nada impede a existencia de vértices que não pertençam nem a S nem a T, e que o menor caminho passe por algum desses vértices.
Não sei se entendi muito bem sua pergunta...
Mas acho que você não considerou que existem vértices que não pertencem nem a S e nem a T... pois não se trata de um corte... por exemplo:
S -> X -> Y -> Z -> T
Os vértices X, Y e Z não pertencem a nenhum dos dois grupos e o único caminho que liga S a T é através deles... então o custo mínimo é a soma de todas estas arestas...
Ajudei em algo?
Mas acho que você não considerou que existem vértices que não pertencem nem a S e nem a T... pois não se trata de um corte... por exemplo:
S -> X -> Y -> Z -> T
Os vértices X, Y e Z não pertencem a nenhum dos dois grupos e o único caminho que liga S a T é através deles... então o custo mínimo é a soma de todas estas arestas...
Ajudei em algo?
Vocês tem razão. Li de novo o enunciado e vi que não dizia nada sobre S e T ser um corte.
Me dei mal.
Me dei mal.