Jump to content
fearz7

[Resolvido] Grafos - Caminho mais seguro

Recommended Posts

fearz7

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.

Share this post


Link to post
Share on other sites
fearz7

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

Share this post


Link to post
Share on other sites
HappyHippyHippo

não estou a perceber a duvida ...

onde está o problema em implementar o BFS usando o parâmetro de qualidade ?


IRC : sim, é algo que ainda existe >> #p@p

Share this post


Link to post
Share on other sites
Rui Carlos

Queres o caminho mais seguro entre dois pontos dados?

Se for isso, eu começava para converter os pesos para uma escala em que menor significasse mais seguro (e.g., fazendo novo_peso = 5 - antigo_peso). E depois era só usar o habitual algoritmo para encontrar o caminho mais curto.

Share this post


Link to post
Share on other sites
Warrior

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?

  • Vote 1

Share this post


Link to post
Share on other sites
Rui Carlos

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.

Share this post


Link to post
Share on other sites
fearz7

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?

Share this post


Link to post
Share on other sites
Rui Carlos

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

Regra geral, há sempre a possibilidade de num grafo específico todos os caminhos terem o mesmo "peso". Aquilo que normalmente se faz nesse caso, é escolher um caminho qualquer.

Share this post


Link to post
Share on other sites
HappyHippyHippo

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

Share this post


Link to post
Share on other sites
Warrior

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

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Restore formatting

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • 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.