Olá Pessoal,
Estou com um problema, tenho que determinar uma rota de carro(ruas a serem percorridas) de um endereço origem e um endereço destino.
Se eu for usar a cidade de Porto Alegre(Rio Grande do Sul) como que eu implemento essa idéia usando grafos.
[]`s
Não sou de Ciências da Computação, mas tive uma matéria com isso. Tive que usar o algoritmo de Dijkstra pra fazer algo parecido. Mas era algo acadêmico e tal, não sei se serve.
O meu problema é academico tbm.
Fala ai como tu implemento a tua solução!!
Penso que terei que cadastrar na mão as rotas, ou tem algo que me ajude com esse problema??
Nem tenho aqui, mas o usuário tinha que construir o grafo na mão, ai ele informava de qual vértice para qual vértice desejava ir, e o algoritmo fazia o resto. Nada demais.
Onde arrumar o mapa para você mesmo fazer o caminho eu não sei.
Se o problema é acadêmico, tu precisa ver o quanto teu professor quer que tu implemente.
Se tu pode pegar uma solução pronta, imagino que as APIs do Google façam isso.
Se for implementar:
Basta popular um grafo imaginando cada intersecção como um nodo de um grafo, e interpretar todas as ruas como vértices entre esses pontos. Isso terá que fazer na mão.
Tem várias frameworks de grafos prontas por aí. Aí é só implementar um algoritmo de busca, leva 10 minutos pra implementar um que faz isso, se for considerar a menor quantidade de ruas como solução.
Olá pessoal,
Segundo o meu professor eu preciso gerar 1.000 vertices no grafo,
tem uma forma de fazer isso sem que tenha que cadastrar na mão.
[quote=MaiqueL]Olá pessoal,
Segundo o meu professor eu preciso gerar 1.000 vertices no grafo,
tem uma forma de fazer isso sem que tenha que cadastrar na mão.[/quote]normalmente nesses casos o professor dá um arquivo e diz para os alunos implementarem algo que interprete o arquivo de parâmetros… assim padroniza os resultados.
pode criar um algoritmo que popule um grafo como se fosse uma malha, ou algum outro padrão que achar interessante… ou usar uma API do google para absorver os dados dos mapas, algo assim.
[quote=gmcouto][quote=MaiqueL]Olá pessoal,
Segundo o meu professor eu preciso gerar 1.000 vertices no grafo,
tem uma forma de fazer isso sem que tenha que cadastrar na mão.[/quote]normalmente nesses casos o professor dá um arquivo e diz para os alunos implementarem algo que interprete o arquivo de parâmetros… assim padroniza os resultados.
pode criar um algoritmo que popule um grafo como se fosse uma malha, ou algum outro padrão que achar interessante… ou usar uma API do google para absorver os dados dos mapas, algo assim.[/quote]
Boa( mas o professor não possou dados para criar o grafo)
Mas lendo a api do Google maps eu vi que posso incrementar a latitude e ir pegando regiões que seriam meus vertices e apartir dessas regiões gerar rotas
vou colocar a mão na massa e ver se isso que eu to pensando funciona.
[]`s
[code]int n, m, c, k, xx, yy, weight, dist[1001];
struct Priority{
bool operator () (int a, int b){
return dist[a] > dist[b]; // attention !
}
};
int main(void){
ios::sync_with_stdio(false);
while(cin >> n >> m >> c >> k && (n+m+c+k)){
//n -> cities, m -> roads, c -> destination, k = start
for(int i = 0; i < n; i++) dist[i] = INF; // set infinity distance
vector<pair><int, int> > cities[n]; // the graph
for(int i = 0; i < m; i++){ // fill the graph, not directed graph
cin >> xx >> yy >> weight;
cities[xx].push_back(make_pair(weight, yy));
cities[yy].push_back(make_pair(weight, xx));
}
dist[k] = 0; // start path, weight = 0
priority_queue<int, vector><int>, Priority> q; // to find the best route O(E+V*Log(V))
q.push(k);
while(!q.empty()){ // the Dijkstra algorithm
int x = q.top(); q.pop();
for(int y = 0; y < cities[x].size(); y++){
if(dist[x] + cities[x][y].first < dist[cities[x][y].second]) {
q.push(cities[x][y].second);
dist[cities[x][y].second] = dist[x] + cities[x][y].first;
}
}
}
cout << dist[c] << endl;
}
return 0;
}
[/code]
Uma solucao para você.