Jump to content

[Resolvido] Grafos - Caminho mais seguro


Recommended Posts

Posted

Boa tarde,

Tenho um determinado grafo pesado direccionado, onde um dos seus pesos corresponde a um atributo qualidade(valor inteiro entre 1 - 5), visto isto, e tendo em conta que quanto mais próximo de 5 estiver maior será a sua qualidade(mais seguro), como é que determino o caminho mais seguro?

Recorro a um algoritmo onde tenho que encontrar o caminho mais longo? Se sim, qual o algoritmo a seguir?

Obrigado desde já pela vossa atenção.

Melhores cumprimentos.

Posted (edited)

Isso eu sei, mas o que me estas a dizer e para escolher a aresta sempre com maior qualidade? Pois eu tenho um determinado vertice como destino.

Edited by fearz7
Posted

Dados 2 caminhos, como é que defines qual é o mais seguro?

Imagina o seguinte exemplo de caminhos entre dois pontos:

5 - 3

4 - 4 - 4

Qual deles é mais seguro?

É uma boa pergunta.

Aliás, nem me tinha apercebido que na sugestão que eu dei (novo_peso = 5 - antigo_peso), mudando o 5 por outro valor (à partida, mais elevado), podia levar a resultados diferentes.

E se calhar até faz mais sentido considerar a segurança de um caminho igual ao peso do arco com menor peso do caminho.

Posted

E se calhar até faz mais sentido considerar a segurança de um caminho igual ao peso do arco com menor peso do caminho.

Desta mesma forma, e se ambos os caminhos tiverem o peso do menor arco igual? O que considero como o caminho mais seguro?

Posted (edited)

Desta mesma forma, e se ambos os caminhos tiverem o peso do menor arco igual? O que considero como o caminho mais seguro?

qual é o mais seguro ?

4-1-4-5

1-4-1-5

eu considero que seria aquele que na, sua totalidade, envolve menos problemas. logo terás sempre de contabilizar todos os arcos.

Edited by HappyHippyHippo
IRC : sim, é algo que ainda existe >> #p@p
Posted (edited)

Tens 3 critérios, tens que os ordenar pela ordem que preferes; isto não é algo que alguém possa decidir por ti/pelo enunciado.

a) maximizar a aresta mais pequena

b) minimizar o número de arestas

c) maximizar o peso das arestas

Tenta ordenar estes caminhos todos para perceberes o que de facto queres:

4-5-1-4

1-5-1

2-5-5-5-5-5-5-5-5

2-3-3-3-3

Edited by Warrior

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
×
×
  • Create New...

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.