Category Archives: Algorithms

Bellman-Ford’s Algorithm

Dijkstra’s algorithm is fast, but limited to non-negatively weighted graph. It also does not applicable for distributed system. Bellman-Ford’s algorithm is the solution for the two problems. It is asymptotically slower than Dijkstra’s algorithm as its complexity is O(EV). However, … Continue reading

Posted in Algorithms, Computer Science | Tagged , , , , | Leave a comment

Dijkstra’s Algorithm

2014/3/5: How stupid I was for not recognizing Dijkstra as a special case of A* without heuristic cost. It makes the algorithm much easier to understand and implement. We only need to consider vertices as states and put them to … Continue reading

Posted in Algorithms, Computer Science | Tagged , , , , , | Leave a comment

8 puzzle A star

Edit: I was completely wrong. After watching the AI’s lectures from UCB, now I know about admissible heuristics function and the trade-off. This classic problem is very interesting. I think if one can solve all of its aspects, he will … Continue reading

Posted in Algorithms, Computer Science | Leave a comment