У меня есть взвешенный граф 30k узлов 160k ребер, без отрицательных весов. Я хотел бы вычислить все кратчайшие пути от всех узлов до других. Я думаю, что не могу использовать какую-либо эвристику для упрощения проблемы.
Я пытался использовать эту реализацию Дейкстры C http://compprog.wordpress.com/2007/12/01/one-source-shortest-path -dijkstras-algorithm / , то есть для одной задачи кратчайшего пути, вызывая функцию dijkstras () для всех моих 30 узлов. Как вы понимаете, это требует времени. На данный момент у меня нет времени писать и отлаживать код самостоятельно, мне нужно как можно скорее вычислить эти пути и сохранить их в базе данных, поэтому я ищу другое более быстрое решение, готовое к использованию, у вас есть какие-нибудь советы?
Мне нужно запустить его на недавнем MacBook Pro с оперативной памятью 8 ГБ, и я хотел бы найти решение, которое займет не более 24 часов, чтобы завершить вычисления.
Заранее большое спасибо !!
Eugenio