最短路径算法大讨论！解决思路
最短路径算法大讨论！！
目前我知道的最短路径算法只有DIJKSTRA算法跟A*算法，算是菜鸟了。前段时间本人优化了下最短路径算法，效率大大提升。不知道DIJKSTRA算法能否算大数据量网络的最短路径。
算大数据量网络最短路径的算法都有哪些？效率如何？
欢迎各位高手进来讨论一二，让我们学习一下！顺带散分~
------解决方案--------------------
高深莫测
------解决方案--------------------
作为一名搞.Net的程序员，我感觉我跑错地方了
------解决方案--------------------
用优先级队列维护带更新节点到已更新集合的距离
------解决方案--------------------
把邻接矩阵改为 vecor<int> ve;速度就提上去，对于稀疏矩阵，速度要快好几倍吧
------解决方案--------------------
最短路径常用的算法就是
两点间的最短距离：Dijkstra(可以用邻接表，处理更简单)
所有点对间的最短距离：Ford-Floyd
------解决方案--------------------
我觉得你要研究的东西有意义，但现实的话，大量节点应该是通过architecture来解决的。
每一个网的节点是有限制的，这样就保证了最短路径算法的时间。相当于是树状的结构。
例如distance vector 算法，在实现的时候最大就是16。
这两个算法应该是network中路由主要两个吧。
scale的问题都是通过architecture的搞定的。
------解决方案--------------------
DIJKSTRA+堆优化，可以大大提高速度
------解决方案--------------------
dijkstra+斐波那契堆
spfa
dijkstra就是a*的一种特殊情况
------解决方案--------------------
应该算慢的，秒级差不多。这种级别的数据量，应该用邻接表+斐波那契堆做优先队列。
（如果是做具体产品，应该在优先队列的优化上多下功夫，有比斐波那契堆更好的方法，不过需要看论文了）
------解决方案--------------------
Floyd：求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。
Dijkstra：求单源、无负权的最短路。时效性较好，时间复杂度O(V^2)。可以用堆优化。
Bellman-Ford：求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。
SPFA：是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。
宽搜：求单源无权最短路。矩阵记录法时间复杂度O(V^2)；边表记录法时间复杂度O(kE)。
稠密图单源无负权最短路：Dijkstra。
稠密图单源有负权最短路：SPFA。
稀疏图单源最短路：SPFA或Bellman-Ford。
多源无负权最短路：Floyd。
多源无权最短路：宽搜。
------解决方案--------------------
慢，路由让你搜个路径2分钟，你干么。
15楼强大。
------解决方案--------------------
双向Dijkstra
双向A*
------解决方案--------------------
在搜索中进行剪枝是必要的，灵活应用，没有现成的答案。
------解决方案--------------------
A*的公式：F=G+H；当H=0时，就是Dijkstra
------解决方案--------------------
高 + 深 。 顶 浅 了。
------解决方案--------------------
vector<pair<int,int> >
------解决方案--------------------
就知道这么两个 还是教材上的 诶 悲剧~~
------解决方案--------------------
lz是数学系的吗?
------解决方案--------------------
谢谢。。 我收咯。。
------解决方案--------------------
学习，收藏
------解决方案--------------------
学习，收藏
------解决方案--------------------
想说的被15楼抢了
------解决方案--------------------
正在慢慢的学习当中
------解决方案--------------------
我走错地方了 帮你顶下
------解决方案--------------------
学习了！！！！
------解决方案--------------------
------解决方案--------------------
内容存入剪贴板
------解决方案--------------------
太弱了。还有双向搜索和分层
------解决方案--------------------
自己也不发个大数据例子来说明一下。太懒。引发不了大讨论
------解决方案--------------------
>就目前我所了解的dijkstra算法结构是介于邻接矩阵的
从来没这种事。dij需要的图结构只要能遍历一个点的所有邻边就行。没人说只能用邻接矩阵。
>该数据结构无法计算包含五万个顶点的网络（我是指用个人的pc机）。
好扯谈。10w个点的稀疏图pc机1秒绝对没问题。当然极端的完全图的话5k个点左右是1秒的极限了。
>这种级别的数据量，应该用邻接表+斐波那契堆做优先队列。
乃太乐观了。就算是稠密图，100w个点的话俺觉得普通堆依然会比fibonacci堆要快。
>如果是做具体产品，应该在优先队列的优化上多下功夫
做具体产品应该在研究数据特点上多下功夫。比如权值大小是否有上限这种。
>双向Dijkstra
>双向A*
俺的经验是这俩东西快不了多少。但是增加的那些代码量嘛，代码能力不强的话debug得多花很多功夫
------解决方案--------------------
学习。。。。
------解决方案--------------------
请教下哦，10w个点的稀疏图pc机1秒绝对没问题? 这遍历点的时间是怎么计算出来。一直不知道pc机的时间和运算时间的计算方法。
------解决方案--------------------
用二叉堆就好了 斐波那契堆实际应用效果不一定好 理论上时间复杂度要优一些而已
双向会快蛮多的 不知道LS是怎么试出的时间差不多
另外如果是要最优解 那跃层这种事情是不用管的
目前我知道的最短路径算法只有DIJKSTRA算法跟A*算法，算是菜鸟了。前段时间本人优化了下最短路径算法，效率大大提升。不知道DIJKSTRA算法能否算大数据量网络的最短路径。
算大数据量网络最短路径的算法都有哪些？效率如何？
欢迎各位高手进来讨论一二，让我们学习一下！顺带散分~
------解决方案--------------------
高深莫测
------解决方案--------------------
作为一名搞.Net的程序员，我感觉我跑错地方了
------解决方案--------------------
用优先级队列维护带更新节点到已更新集合的距离
------解决方案--------------------
把邻接矩阵改为 vecor<int> ve;速度就提上去，对于稀疏矩阵，速度要快好几倍吧
------解决方案--------------------
最短路径常用的算法就是
两点间的最短距离：Dijkstra(可以用邻接表，处理更简单)
所有点对间的最短距离：Ford-Floyd
------解决方案--------------------
我觉得你要研究的东西有意义，但现实的话，大量节点应该是通过architecture来解决的。
每一个网的节点是有限制的，这样就保证了最短路径算法的时间。相当于是树状的结构。
例如distance vector 算法，在实现的时候最大就是16。
这两个算法应该是network中路由主要两个吧。
scale的问题都是通过architecture的搞定的。
------解决方案--------------------
DIJKSTRA+堆优化，可以大大提高速度
------解决方案--------------------
dijkstra+斐波那契堆
spfa
dijkstra就是a*的一种特殊情况
------解决方案--------------------
应该算慢的，秒级差不多。这种级别的数据量，应该用邻接表+斐波那契堆做优先队列。
（如果是做具体产品，应该在优先队列的优化上多下功夫，有比斐波那契堆更好的方法，不过需要看论文了）
------解决方案--------------------
Floyd：求多源、无负权边的最短路。用矩阵记录图。时效性较差，时间复杂度O(V^3)。
Dijkstra：求单源、无负权的最短路。时效性较好，时间复杂度O(V^2)。可以用堆优化。
Bellman-Ford：求单源最短路，可以判断有无负权回路（若有，则不存在最短路），时效性较好，时间复杂度O（VE）。
SPFA：是Bellman-Ford的队列优化，时效性相对好，时间复杂度O（kE）。（k<<V）。
宽搜：求单源无权最短路。矩阵记录法时间复杂度O(V^2)；边表记录法时间复杂度O(kE)。
稠密图单源无负权最短路：Dijkstra。
稠密图单源有负权最短路：SPFA。
稀疏图单源最短路：SPFA或Bellman-Ford。
多源无负权最短路：Floyd。
多源无权最短路：宽搜。
------解决方案--------------------
慢，路由让你搜个路径2分钟，你干么。
15楼强大。
------解决方案--------------------
双向Dijkstra
双向A*
------解决方案--------------------
在搜索中进行剪枝是必要的，灵活应用，没有现成的答案。
------解决方案--------------------
A*的公式：F=G+H；当H=0时，就是Dijkstra
------解决方案--------------------
高 + 深 。 顶 浅 了。
------解决方案--------------------
vector<pair<int,int> >
------解决方案--------------------
就知道这么两个 还是教材上的 诶 悲剧~~
------解决方案--------------------
lz是数学系的吗?
------解决方案--------------------
谢谢。。 我收咯。。
------解决方案--------------------
学习，收藏
------解决方案--------------------
学习，收藏
------解决方案--------------------
想说的被15楼抢了
------解决方案--------------------
正在慢慢的学习当中
------解决方案--------------------
我走错地方了 帮你顶下
------解决方案--------------------
学习了！！！！
------解决方案--------------------
------解决方案--------------------
内容存入剪贴板
------解决方案--------------------
太弱了。还有双向搜索和分层
------解决方案--------------------
自己也不发个大数据例子来说明一下。太懒。引发不了大讨论
------解决方案--------------------
>就目前我所了解的dijkstra算法结构是介于邻接矩阵的
从来没这种事。dij需要的图结构只要能遍历一个点的所有邻边就行。没人说只能用邻接矩阵。
>该数据结构无法计算包含五万个顶点的网络（我是指用个人的pc机）。
好扯谈。10w个点的稀疏图pc机1秒绝对没问题。当然极端的完全图的话5k个点左右是1秒的极限了。
>这种级别的数据量，应该用邻接表+斐波那契堆做优先队列。
乃太乐观了。就算是稠密图，100w个点的话俺觉得普通堆依然会比fibonacci堆要快。
>如果是做具体产品，应该在优先队列的优化上多下功夫
做具体产品应该在研究数据特点上多下功夫。比如权值大小是否有上限这种。
>双向Dijkstra
>双向A*
俺的经验是这俩东西快不了多少。但是增加的那些代码量嘛，代码能力不强的话debug得多花很多功夫
------解决方案--------------------
学习。。。。
------解决方案--------------------
请教下哦，10w个点的稀疏图pc机1秒绝对没问题? 这遍历点的时间是怎么计算出来。一直不知道pc机的时间和运算时间的计算方法。
------解决方案--------------------
用二叉堆就好了 斐波那契堆实际应用效果不一定好 理论上时间复杂度要优一些而已
双向会快蛮多的 不知道LS是怎么试出的时间差不多
另外如果是要最优解 那跃层这种事情是不用管的