leetcode(7):图论Dijkstra||
这里写自定义目录标题
图论问题一般分为：
- 单源最短路径问题：从某固定源点出发，求其到所有其他顶点的最短路径
- （有向）无权图
- （有向）有权图
- 多源最短路径问题：求任意两顶点间的最短路径
1.迪杰斯特拉Dijkstra
有权图的单源最短路径算法——dijkstra；
不能处理带负边权的情况，用邻接矩阵或邻接表存图
——————————————————————————
所以 最短路径，无向图，正边权——Dijkstra算法
———————————————————————————
Dijkstra进行进一步的堆优化以后时间复杂度成为O(nlogn)，
Floyd的O(n^3)
Dijkstra，以及常用的还有Bellman-Ford，SPFA等均是在求单源最短路径的问题中有着较为理想的时间复杂度(<=O(n^2))，
但若是求图中任意两点间的距离，尤其是在图较为稠密时，Floyd的O(n^3)也是不输于其他的。