最短路径算法大讨论！！
目前我知道的最短路径算法只有DIJKSTRA算法跟A*算法，算是菜鸟了。前段时间本人优化了下最短路径算法，效率大大提升。不知道DIJKSTRA算法能否算大数据量网络的最短路径。
算大数据量网络最短路径的算法都有哪些？效率如何？
欢迎各位高手进来讨论一二，让我们学习一下！顺带散分~
[解决办法]
高深莫测
[解决办法]
作为一名搞.Net的程序员，我感觉我跑错地方了
[解决办法]
用优先级队列维护带更新节点到已更新集合的距离
[解决办法]
[解决办法]
最短路径常用的算法就是
两点间的最短距离：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。
多源无权最短路：宽搜。
[解决办法]
[解决办法]
双向Dijkstra
双向A*
[解决办法]
在搜索中进行剪枝是必要的，灵活应用，没有现成的答案。
[解决办法]
[解决办法]
高 + 深 。 顶 浅 了。
[解决办法]
vector<pair<int,int> >
[解决办法]
就知道这么两个 还是教材上的 诶 悲剧~~
[解决办法]
lz是数学系的吗?
[解决办法]
谢谢。。 我收咯。。
[解决办法]
学习，收藏
[解决办法]
学习，收藏
[解决办法]
[解决办法]
正在慢慢的学习当中
[解决办法]
我走错地方了 帮你顶下
[解决办法]
学习了！！！！
[解决办法]
[解决办法]
内容存入剪贴板
[解决办法]
太弱了。还有双向搜索和分层
[解决办法]
自己也不发个大数据例子来说明一下。太懒。引发不了大讨论
[解决办法]
>就目前我所了解的dijkstra算法结构是介于邻接矩阵的
从来没这种事。dij需要的图结构只要能遍历一个点的所有邻边就行。没人说只能用邻接矩阵。
>该数据结构无法计算包含五万个顶点的网络（我是指用个人的pc机）。
好扯谈。10w个点的稀疏图pc机1秒绝对没问题。当然极端的完全图的话5k个点左右是1秒的极限了。
>这种级别的数据量，应该用邻接表+斐波那契堆做优先队列。
乃太乐观了。就算是稠密图，100w个点的话俺觉得普通堆依然会比fibonacci堆要快。
>如果是做具体产品，应该在优先队列的优化上多下功夫
做具体产品应该在研究数据特点上多下功夫。比如权值大小是否有上限这种。
>双向Dijkstra
>双向A*
俺的经验是这俩东西快不了多少。但是增加的那些代码量嘛，代码能力不强的话debug得多花很多功夫
[解决办法]
学习。。。。
[解决办法]
[解决办法]
用二叉堆就好了 斐波那契堆实际应用效果不一定好 理论上时间复杂度要优一些而已
双向会快蛮多的 不知道LS是怎么试出的时间差不多
另外如果是要最优解 那跃层这种事情是不用管的
[解决办法]
LZ这稀疏矩阵 没必要搞邻接表了吧
[解决办法]
不错不错.学习学习
[解决办法]
>请教下哦，10w个点的稀疏图pc机1秒绝对没问题?
比如10w个点20w条边这种图，cpu只要是p4级别或以上的，没写进1秒的那基本都是自己写扯了。
>这遍历点的时间是怎么计算出来。
加普通堆的dij是ElogV，自己把E=20w,V=10w代进去，10^7的量都没到，1秒肯定是有信心的。
[解决办法]
完全技术贴，学习中
[解决办法]
学习的好东本
[解决办法]
其实算路应用最多的是在导航软件中，一般在pc机上需要1秒以上的到了设备上的时间就无法忍受了。
另外问下双向dijkstra真的比单向的快吗，我怎么觉得是一样的时间其实
[解决办法]
学习，学习，收藏。
[解决办法]
学习了！！！
[解决办法]
印象中有个什么模仿蚂蚁的算法
[解决办法]
收藏，继续关注
[解决办法]
学习了
------解决方案--------------------
[解决办法]
同学面试的时候问到了这个题。。。。。当时觉得很无语。。。。我觉得这是科学家研究的问题
[解决办法]
zheshigehaodongxi
[解决办法]
学习，收藏了。
好贴。
[解决办法]
留名。。。。。
[解决办法]
[解决办法]
[解决办法]
用二叉堆就好了 斐波那契堆实际应用效果不一定好 理论上时间复杂度要优一些而已
双向会快蛮多的 不知道LS是怎么试出的时间差不多
另外如果是要最优解 那跃层这种事情是不用管的
[解决办法]
不懂 ，学习下了
[解决办法]
太强大了
[解决办法]
看看算法设计的教程，对各类算法的效率都有评价的。
[解决办法]
好高深
[解决办法]
做为.net程序员
我不应该点进来的
[解决办法]
早还给老师了...
mark
[解决办法]
楼主代码for循环嵌套太多
[解决办法]
一试
- C/C++ code
void Min_path(long **cost = new long * [vertexNumber], long **path = new long * [vertexNumber]){ /******************************************************用于精确计算运行时间*********************************************************************/ QueryPerformanceFrequency(&Frequency); QueryPerformanceCounter(&BegainTime) ; /******************************************************用于精确计算运行时间*********************************************************************/ long i , j ,u , v , E , min , count , n = vertexNumber ; long s[vertexNumber] ; long pos[vertexNumber] ; long dist[vertexNumber] ; // cout << "Start Point and End Point :" ; // cin >> v >> E ; v = 236; E = 542; for (i = 0 ; i < n ; i ++) { s[i] = 0 ; dist[i] = cost[i][v - 1] ; path[i][0] = v - 1 + 1 ; pos[i] = 0 ; } s[v - 1] = 1 ; dist[v-1] = 0 ; for (count = 1 ; count < n ; count ++) { min = MAXINF ; for (i = 0 ; i < n ; i ++) { if (s[i] == 0 && dist[i] < min) { u = i ; min = dist [i] ; } } s[u] = 1 ; path[u][++ pos[u]] = u + 1 ; for (i = 0 ; i < n ; i ++) { if (s[i] == 0) { if (dist[u] + cost[i][u] < dist[i] && cost [i][u] < MAXINF) { dist[i] = dist[u] + cost[i][u] ; for (j = 0 ; j <= pos[u] ; j ++) { path[i][j] = path[u][j] ; } pos[i] = pos[u] ; } } } } /******************************************************用于精确计算运行时间*********************************************************************/ QueryPerformanceCounter(&EndTime); cout << "Dijkstra 算法的运行时间（单位：s）：" <<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl; /******************************************************用于精确计算运行时间*********************************************************************/ for (i = 0 ; i <= pos[E - 1] ; i ++) { cout << path[E - 1][i] << "," ; } cout << "\t" ; cout << dist[E - 1] ; cout << endl ; system("pause");}
[解决办法]
看不懂
[解决办法]
？？？？？？？？？？？？？？？？
[解决办法]
好高深。。学习！
[解决办法]
看不懂的路过
[解决办法]
帮你们顶一下吧。
[解决办法]
正在学习中。
[解决办法]
目前应用比较广泛的导航算法应该是双向A*算法， 优化来讲基本是对图进行提层， 另外A*算法中加入方向扩展的控制（加入期望 过滤可能性小的node点）。 当A*扩展点是遇到重要的连通点是 就往上层图跳转 继续A* 一直到双向碰撞为止。 基本上很多的优化都是基于这种思想
[解决办法]
帮你们顶一下吧。
[解决办法]
路过，看高见。
[解决办法]
深奥啊！
[解决办法]
接分啊接分~~~
[解决办法]
学习了！
[解决办法]
还是有些价值！
[解决办法]
看不懂啊
[解决办法]
学习一下再来
[解决办法]
我的妈呀···
都是高手啊·
[解决办法]
厉害，，