今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。
又把昨天的bellman-ford算法看了一遍,比昨天理解的又透彻一些。
这两个算法都是单源最短路,就是固定一个起点,然后求这个点到其他所有点的最短距离的意思。
由于固定一个起点,首先应该想到的是先计算靠近它的点,然后往远处求。
所以根据这个思路写出一个递推式:记从起点s到顶点i的最短距离为d[i],
d[i]=min{d[j]+ (顶点j到i的权值)|e=(j,i)∈E }
今天读的挑战程序设计竞赛的图的最短路问题,只看了一个dijkstra算法,但没怎么看明白。
又把昨天的bellman-ford算法看了一遍,比昨天理解的又透彻一些。
这两个算法都是单源最短路,就是固定一个起点,然后求这个点到其他所有点的最短距离的意思。
由于固定一个起点,首先应该想到的是先计算靠近它的点,然后往远处求。
所以根据这个思路写出一个递推式:记从起点s到顶点i的最短距离为d[i],
d[i]=min{d[j]+ (顶点j到i的权值)|e=(j,i)∈E }
本文标题:挑战程序设计竞赛11.7
本文链接:https://www.haomeiwen.com/subject/cooouttx.html
网友评论