1)常用的图最短路径的算法有两个:Dijkstra算法和Floyd算法; 2)Dijkstra算法适用于求图中两节点之间最短路径,Floyd算法适于求图中任意两节点间; 3)两种算法的主要思想是动态规划,而Dijkstra算法设计比较巧妙的是:在求源节点到终结点自底向上的过程中,源节点到某一节点之间最短路径的确定上(这也是我之前苦于没有解决的地方),其解决方法是通过比较每次循环中源节点到各个节点的权值来找出最小值即最短路径,然后再对各个权值进行修正,再循环。。。这种求最短路径的方式与图最小生成树算法之Kruskal…

2013年10月26日 0条评论 0点热度 阅读全文

深度遍历: 从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。 其更适合:目标比较明确,以找到目标为主要目的的情况。 广度遍历: 类似于树中的层序遍历,首先遍历完和某一顶点v相连的所有顶点,然后再遍历和这些顶点相连的顶点,以此类推。 其更适合于:不断扩大遍历范围时找到相对最优解的情况。 具体代码如下: // GraphSearch.cpp : Defines the entry point for the console applicatio…

2013年10月25日 0条评论 0点热度 阅读全文

深度遍历: 从图中某个顶点v出发,访问此顶点,然后从v的未被访问的邻接点出发深度优先遍历图,直至图中所有和v有路径相通的顶点都被访问到。 其更适合:目标比较明确,以找到目标为主要目的的情况。 广度遍历: 类似于树中的层序遍历,首先遍历完和某一顶点v相连的所有顶点,然后再遍历和这些顶点相连的顶点,以此类推。 其更适合于:不断扩大遍历范围时找到相对最优解的情况。 具体代码如下: // GraphSearch.cpp : Defines the entry point for the console applicatio…

2013年10月25日 0条评论 0点热度 阅读全文