图论:最短路算法有哪些以及它们的比较?

来源:学生作业帮助网 编辑:作业帮 时间:2024/03/02 19:07:45

图论:最短路算法有哪些以及它们的比较?
图论:最短路算法有哪些以及它们的比较?

图论:最短路算法有哪些以及它们的比较?
弗洛伊德 n^3 的时间把n个点两两的最短路求出来
迪杰斯特拉 n^2的时间(用堆优化到Nlog(M),M是边数),单源最短路,但是不能对付有负权的图
SPFA,M*k的时间(K是一个常数),单源最短路,能对付有负权的图
感觉常用的就这三个了吧.

单源最短路径,即计算从固定一点出发到其他点的最短距离,可用贪婪算法(贪心算法)。
-_- 哎.. 记在脑子里的就这个.. 其他的忘光了...