weixin_45453175的博客

原创 OI最短路问题（迪杰斯特拉算法）

@迪杰斯特拉算法 在OI比赛中有许多图论问题，求最短路径就是一类。最短路径有许多的求法，比如回溯、Floyd算法（弗洛伊德算法）、bellman算法、SPFA算法和Dijkstra（迪杰斯特拉算法）等 因为回溯与其他算法时间复杂度高得多，所以我们在除了不会写只能暴力的情况下是不考虑通过回溯来求最短路。Floyd算法可以计算负权值，而且时间复杂度要比Dijkstra算法快那么一丢丢（几乎可以忽略不计...