Hola, estoy haciendo una cosilla de programacion, que tiene que correr en una maquina limitada.
Estoy haciendo calculando el flujo maximo que puede tener un grafo de unos 60000 vertices y unos 3 o 4 millones de aristas. Estoy utilizando bfs(recorrido en amplitud, si no me equivoco) vamos Edmonds-karp. Representando los grafos con listas de adyacencia, ya que con matrices seria imposible(El equipo en el que tengo que correrlo es un pentium3 800Mhz con 350MB RAM + 350MB de memoria paginada).
Actualmente me funciona pero deberia rebajar el tiempo, sabeis alguna forma de optimizar este algoritmo o la representacion de grafos?
Gracias
Pues mas optimo que las listas de adyacencia no se que habra, porq ya de por si son dinamicas y ocupan lo necesario y nada mas...
Un preprosesamiento siempre ayuda, la idea seria eliminar caminos de flujo superfluos ... y según mal recuerdo usando un goloso en vez del bfs puedes mejorarlo mucho mas. No recuerdo los nombres de los algoritmos ahora mismo :(
Hola!
has mirado si en el Cormen hablan algo de optimizar EK? Un saludo!
Vicente
Esta bastante bien el Cormen, ya lo conocia pero de optimizacion del EK no he visto nada, pero he visto el push-relabel que para mi caso es bastante bueno pues con el mio tiene un coste vertices x aristas^2 y con este vertices^3 o (vertices^2) x aristas, que para mi problema es bastante bueno.
Wenas yo de nuevo, tenia una preguntilla, hay alguna manera de darle opciones al compilador(gcc) para que te haga un codigo mas eficiente para determinada maquina(en mi caso pentium 3) a parte de la -static que es para compilar incluyendo las librerias dinamicas.