算法导论系列:贪心算法(2)

这篇文章我们将来一起看看贪心算法一个具体例子, Dijkstra算法

Dijkstra算法最著名的应用是解决单元最短路径,这是一类贪心算法,他先是求出长度最短的一条路径,然后参照这一条最短路径去求出长度次短的路径,知道求出从起点到各个定点的最短路径.

这个算法不仅仅是贪心算法,其实也是一种特殊的动态规划,动态规划的本质是独立的子问题,而贪心每次可以求得最优的独立子问题,这两者有一些交集,但是收到很多约束,会影响适应的范围.

举例:今天你去一个景点去玩,景点地图如下,假如你从1号点出发,那到达其他各个节点的最短路径是什么?

现在我们假设景点地图如上所示,从起点到下一个点都会有具有方向路径和相应的权重,我们可以使用矩阵进行表示,如下图所示:

下图是算法的过程(用电子屏幕写字果然很不舒服):

最终的路径为:

代码如下:

运行结果:

1:输入样例

2:输出结果

下一篇文章我们将一起学习下哈夫曼编码