算法3——图、最短路、最小生成树.ppt

《算法3——图、最短路、最小生成树.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、算法3讲师：刘少凡目录图最短路算法最小生成树图图由顶点(vertex,node)和边(edge)组成。顶点集合是V，边的集合是E的图记做G=(V,E)，连接两点u和v的边用e=(u,v)表示边有指向性的图为有向图边无指向性的图为无向图图的表示方法邻接矩阵与邻接表选择哪一种方法？邻接矩阵优点：便于查找两顶点是否相连，程序编写简单缺点：浪费大量空间邻接表优点：节省空间缺点：查询两顶点是否相连需要遍历，程序编写较困难视情况而定目录图最短路算法最小生成树最短路问题一般为给定两个顶点，以这两个顶点为起点和终点的路径中，求边

2、的权值和最小的那条路径（或者只需要求最短距离）。单源最短路径问题固定一个起点，求它到其他所有点的最短路的问题。算法1：Bellman-Ford算法算法2：Dijkstra算法Bellman-Ford算法代码实现示例假设A为源点初始d={0,INF,INF,INF,INF,INF,INF}第一轮遍历结束d={0,2,5,INF,INF,INF,INF}第二轮遍历结束d={0,2,5,7,12,INF,INF}第三轮遍历结束d={0,2,5,7,12,8,17}第四轮遍历结束d={0,2,5,7,11,8,16}注：

3、真实算法计算情况会因边的遍历顺序不同而不同复杂度每轮更新至少都能确定到某一个点的最短路径，所以最多会更新V-1轮，每轮都会遍历E条边，所以复杂度为O(V*E)另外，如果图中有负圈，第V轮更新依然会更新d的值，可以利用这个性质来检查图中是否有负圈Dijkstra算法算法思想：找到最短距离已经确定的顶点，从它出发更新相邻顶点的最短距离，从此后不再关心该最短距离已经确定的点（需要图中不存在负边）如何寻找最短距离已经确定的顶点？最开始时，只有源点的最短距离是确定的。在之后，尚未使用过的顶点中，距离d[i]最小的顶点就是最

4、短距离已经确定的顶点代码实现复杂度While循环每次会使用一个点作为v，直到所有点都用过，会循环V次内层循环会循环V次复杂度为O(V*V)Bellman-Ford算法复杂度为O(V*E)当V

5、循环操作。for循环内的操作相当于被执行了E次，每次更新操作复杂度为O(logV)，所以总复杂度为O(E*logV)Bellman-Ford算法复杂度为O(V*E)第二份代码实现的dijkstra算法更快那么第二份代码与第一份代码的区别是什么？采用了堆（优先队列）的数据结构，优化了取出最小值和距离更新操作优选数据结构很重要总结对于不存在负边的图，可以使用Dijkstra算法解决单源最短路径问题对于不存在负圈的图，可以使用Bellman-Ford算法解决单源最短路径问题对于存在负圈的图？不存在最短路径，因为每绕负圈

6、一周都可以使路径减小任意两点间的最短路问题前面介绍的Bellman-Ford算法和Dijkstra算法都是解决的单源最短路径问题，那么如何求任意两点间的最短路径呢？方法1：将每个点作为源点，分别用Bellman-Ford算法或Dijkstra算法进行计算，复杂度O(E*V^2)或O(E*V*logV)方法2：Floyd-Warshall算法Floyd-Warshall算法算法思想：DPd[i][j]=min(d[i][j],d[i][k]+d[k][j])d[i][j]表示i到j的最短距离上式表示的意思是，i到j

7、的最短距离，要么就是目前i到j的距离，要么就是i到k的最短距离加上k到j的最短距离(k为除i和j之外的任意点)代码实现复杂度三重循环，O(V^3)一般情况下优于方法1采用Bellman-Ford算法的情况（因为一般情况下V

8、可得到最短路径目录图最短路算法最小生成树最小生成树（MST,MinimunSpanningTree)给定一个无向图，如果它的子图中任意两个顶点都互相连通并且是一棵树，那么这棵树就叫做生成树。如果边上有权值，那么使得边的权值和最小的生成树叫做最小生成树常见的应用场景：修路问题，旅游问题等算法1：Prim算法算法2：Kruskal算法Prim算法算法思想假设有一颗只包含顶点v