Introduction
The Liao-Wong Algorithm and Bellman-Ford Algorithm are two algorithms for longest paths problem I touched through school work. There are many algorithms I learned through classes. I believe they will be useful for the future. Since I spent time to understand them, I think it is worth to spent sometime to collect and organize them here. It will be easy for me to review them later.
There are a lot of algorithm for shortest paths. Longest paths are a little bit complex problem to handle.
Bellman-Ford Algorithm
Bellman-Ford Algorithm is very straight forward algorithm from shortest paths. The idea is switching the positive and negative weights for the paths. Then using the shortest paths algorithm to find out the shortest path. Change it pack to positive weight. It is the longest path.
Liao-Wong Algorithm
Liao-Wong Algorithm needs to ignore the negative weight paths firstly. Find the longest path only with the positive weight paths. Then adding the negative weight paths and adjust the solutions.
If you have any questions, please contact with tianluwu@gmail.com