SoloCodigo
Programación General => C/C++ => Mensaje iniciado por: NightFox en Viernes 27 de Abril de 2007, 07:59
-
Necesito diseñar un software en C y necesito ayuda ya que no se como programar grafos dirigidos, solo se diseñar listas simples, enlazadas, circulares, pilas y colas, ojalaque esos conocimientos me sirvan de algo, pero el problema radica en que no se como hacerlo ya que necesito usar grafos, a continuacion expongo el problema, si alguien me puede ayudar por favor enviarme un email:
Un empresa de transportes atiende a un numero de ciudades, las que deben estar conectadas entre si por buses y aviones. Si existe un vuele de la ciudad i a la ciudad j, tambien existe un bus de la ciudad i a la j y de la j a la i, pero no necesariamente existe un avion de la ciudad j a la i.
Los vuelos pueden tener escalas.
1.- Diseñar un grafo que contenga las ciudades y que ademas tenga:
10.000 ciudades que pueden ser generadas en forma aleatoria.
Mediante una matriz de adyacencia indica la relacion entre los vertices, que debe ser creada en forma aleatoria.
En base a la informacion generada en los puntos anteriores etiquete entre 1 y 100 los costos de los arcos. Todos los costos entre [1,500] equivalen a viajes en bus, los superiores a 500 equivalen a viajes en avion.
Guarde su grafo en un archivo llamado "grafo.txt" de la siguiente forma :
Vertice1,Vertice2, (ini,fin)
Eje
1,2(2,1) indicara 2------->1.
2.- El programa ademas debe tener:
Una funcion que tome el archivo "grafo.txt" y cree una lista de adyacencia y guarde los resultados en un archivo llamado "lista.txt" que debe tener el siguiente formato:
Nodo1>Nodo2,Nodo3...
Nodo2>Nodo5,Nodo5...
El programa debe solicitar indicar el punto de origen y de partida, en base a esto el programa debe indicar la ruta mas economica, indicando todas las escalas si es que las hay, indicando si se usa bus, avion, ambas y cuanto de cada una.
Utilice el algoritmo Dijkstra.
POR FAVOR AYUDA SOLO EN ENTENDER COMO SE HACE.
SE AGRACEDE AYUDA.
-
Ya leiste algo de teoría (http://es.wikipedia.org/wiki/Teor%C3%ADa_de_grafos)?
Esta tambien (http://www.monografias.com/trabajos/grafos/grafos.shtml)...
Un saludo
-
pues si, la verdad si no sabes nada de grafos, lo primero que tenej que hacer es aprender como funcionan, que hacen, por que existen, que simplifican, y despues meterte a tratar de hacerlo en un lenguaje de programacion
Aqui (http://www.fceia.unr.edu.ar/estruc/2006/graffund.htm) hay algo mas, tambien aqui. (http://www.dis.um.es/~ginesgm/temas/tema4-1/index.htm)
BYTE.
-
:lol: :lol:
y hay mas...
http://search.freefind.com/find.html?id=65...query=grafos&s= (http://search.freefind.com/find.html?id=6585932&pageid=r&mode=ALL&n=0&query=grafos&s=)