没有合适的资源?快使用搜索试试~ 我知道了~
Geeks : Dijkstra’s Algorithm for Adjacency List Representation 最...
需积分: 10 1 下载量 71 浏览量
2014-08-02
18:59:13
上传
评论
收藏 8KB TXT 举报
温馨提示
试读
10页
最短路径的O(ElgV)的解法。 使用邻接表存储图,使用堆操作选取下一个最小路径点。 本题的难度并不在最短路径本身这个算法,而是在于堆的操作: 1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。 2 使用一个数组记录当前顶点在堆中的位置,相当于一个hash表了,可以需要的时候,直接从表中查找表示顶点的堆节点在堆中的位置,要记得更新节点时维护好这个表。 3 释放内存的时候注意,弹出堆的节点可以马上释放,不过注意不要双重释放内存了 记得曾经看到网上有人说堆排序是百万年薪的算法,不过现在看来光是堆排序是非常简单的算法了,会堆排序应该得达不到百万年薪吧,因为现在的算法高手应该都能随手写出堆排序的算法。 但是如本题这样灵活运用堆还是十分困难的。 参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
资源推荐
资源详情
资源评论
Geeks : Dijkstra’s Algorithm for Adjacency List Representation 最短路径
最短路径的O(ElgV)的解法。
使用邻接表存储图,使用堆操作选取下一个最小路径点。
本题的难度并不在最短路径本身这个算法,而是在于堆的操作:
1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。
2 使用一个数组记录当前顶点在堆中的位置,相当于一个hash表了,可以需要的时候,直接从表中查找表示顶点的堆节点在堆中的位置,要记得更新节点时维护好这个表。
3 释放内存的时候注意,弹出堆的节点可以马上释放,不过注意不要双重释放内存了
记得曾经看到网上有人说堆排序是百万年薪的算法,不过现在看来光是堆排序是非常简单的算法了,会堆排序应该得达不到百万年薪吧,因为现在的算法高手应该都能随手写出堆排序的算法。
但是如本题这样灵活运用堆还是十分困难的。
参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
最短路径的O(ElgV)的解法。
使用邻接表存储图,使用堆操作选取下一个最小路径点。
本题的难度并不在最短路径本身这个算法,而是在于堆的操作:
1 使用双重指针操作堆的节点,可以省去直接复制操作堆节点,提高效率,并且这才是有效操作动态地址数据的方法,不用双重指针,我思考了下,觉得更加不好做。
2 使用一个数组记录当前顶点在堆中的位置,相当于一个hash表了,可以需要的时候,直接从表中查找表示顶点的堆节点在堆中的位置,要记得更新节点时维护好这个表。
3 释放内存的时候注意,弹出堆的节点可以马上释放,不过注意不要双重释放内存了
记得曾经看到网上有人说堆排序是百万年薪的算法,不过现在看来光是堆排序是非常简单的算法了,会堆排序应该得达不到百万年薪吧,因为现在的算法高手应该都能随手写出堆排序的算法。
但是如本题这样灵活运用堆还是十分困难的。
参考:http://www.geeksforgeeks.org/greedy-algorithms-set-7-dijkstras-algorithm-for-adjacency-list-representation/
[cpp] view plaincopy
01.#include <stdio.h>
02.#include <limits>
03.
04.class Dijsktra_Adjacency_List_and_Head
05.{
06. struct Node
07. {
08. int des, weight;
09. Node *next;
10. Node(int d, int w) : des(d), weight(w), next(NULL) {}
11. ~Node()
12. {
13. if (next) delete next;
14. next = NULL;
15. }
16. };
17.
18. struct AdjList
19. {
20. Node *head;
21. AdjList() : head(NULL) {}
22. ~AdjList()
23. {
24. if (head) delete head;
25. head = NULL;
26. }
27. };
剩余9页未读,继续阅读
资源评论
feng_ge18
- 粉丝: 2
- 资源: 2
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功