7

Estou tentando resolver este problema de programação.

Em resumo, o problema descreve diversas linhas de ônibus como um grafo não direcionado e fala que a passagem de um ônibus custa 1 real. Alguém pode me dar uma dica de como posso obter o menor custo em reais que sai de um no A para o no B ?

Nao consegui pensar em nenhuma estratégia usando uma busca em largura.

Nesse exemplo abaixo o menor valor para sair de A para B seria 2 reais. 1 real com uma passagem pela linha vermelha e outro real por uma passagem da linha azul. Exemplo

2 Respostas 2

3

A primeira coisa que você deve perceber no problema é que o custo entre as diversas linhas de ônibus é sempre 1, então você não precisa nem mesmo utilizar o algoritmo de Dijkstra ou qualquer outro algoritmo de caminho mais curto genérico. Uma simples Busca em Largura é o suficiente e mais rápida.

O segundo ponto importante é como construir seu grafo. Pelo enunciado do problema você consegue perceber que um Câmpus é ligado à X outros campi por uma linha de ônibus, a qual você pode utilizar por tempo indefinido (desde que não saia da linha) para andar entre todos os campi conectados por tal linha. O que isso lhe diz é: todos os vértices (os campi) de uma linha de ônibus têm acesso a todos os outros vértices, ou seja, são conectados no grafo, com arestas de peso 1.

Pegando a entrada de exemplo do problema:

9 4
6 2 3 4 6 7 9
4 1 3 4 5
3 8 3 4
2 9 8

Na segunda linha temos 2 3 4 6 7 9 (podemos ignorar o 6 aqui, pois ele só é utilizado para informar quantos vértices estão presentes na linha). Todos esses vértices apresentados podem chegar a qualquer um dos outros vértices pagando apenas um preço de 1, então a representação dessas conexões em uma matriz de adjacência fica da seguinte forma:

   | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
    --- --- --- --- --- --- --- --- ---
 1 |   |   |   |   |   |   |   |   |   |

 2 |   |   | T | T |   | T | T |   | T |

 3 |   | T |   | T |   | T | T |   | T |

 4 |   | T | T |   |   | T | T |   | T |

 5 |   |   |   |   |   |   |   |   |   |

 6 |   | T | T | T |   |   | T |   | T |

 7 |   | T | T | T |   | T |   |   | T |

 8 |   |   |   |   |   |   |   |   |   |

 9 |   | T | T | T |   | T | T |   |   |

onde T indica que há uma aresta conectando dois vértices, e a ausência de T indica que não é possível chegar de um vértice a outro (esse grafo representa apenas as conexões dadas pela primeira linha de ônibus do exemplo!).

Resumindo: na hora de ler a entrada do problema, construa seu grafo de forma que todos os Campi de uma linha tenham acesso a todos os outros Campi da mesma linha. E execute uma Busca em Largura sobre o grafo. Isso lhe dará a resposta correta.

1

Sua pergunta não tem uma resposta simples porque este problema de grafos não é simples.

Você deve usar algum algoritmo que resolva o "Problema do Caminho Mínimo" (inglês: Shortest path problem).

Não sei qual dos dois seria mais rápido em seu caso, então, tente um dos dois:

  1. Dijkstra: https://pt.wikipedia.org/wiki/Algoritmo_de_Dijkstra
  2. A*: https://pt.wikipedia.org/wiki/Algoritmo_A*

Se você pesquisar em inglês, seria mais fácil. Exemplo: Dijkstra em Java.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .