公考最短路径原理(最短路径原理行测)

2004年，世界著名科学杂志《物理世界》举行了一场别开生面的评选活动，邀请世界各地的读者评选出自己心目中最伟大、最喜爱的公式、定理或定律。最终的结果出乎很多人的意料，连幼儿园的小孩都知道的公式“1+1=2”不仅入选，而且还高居第一。无独有偶，尼加拉瓜这个国家在鼎盛时期发行了一套纪念邮票《改变世界面貌的十个数学公式》，排在第一位仍然是“1+1=2”这个公式。下面中公教育专家带大家来看看这个公式是如何解决公务员考试行测中“最短路径问题”的。

“最短路径问题”是公务员考试数学运算经常涉及的一种题型。所谓最短路径问题是指在行程路线中，如何确定从某处到另一处最短路线的条数。比如：

【例】下图是一个街道的平面图，纵横各有7条路， 某人从最左上处的点到最右下处，共有多少条最短路线?

为方便大家理解，中公教育专家先从纵横各有2条路开始讲起，如下图：

注：第一行街道交叉点分别用A1、A2、A3表示，第二行街道交叉点分别用B1、B2、B3表示，第三行街道分别用C1、C2、C3表示。

如果从最左上角(A1)到最右下角(C3)所走路径最短，则该人只能往右走或往下走，不能走回头路。因为如果走回头路，所走路线肯定不是最短。按照只能往右走或 往下走，最短路线有：A1-A2-A3-B3-C3、A1-A2-B2-B3-C3、A1-A2-B2-C2-C3、A1-B1-B2-B3-C3、A1-B1-B2-C2-C3、

A1-B1-C1-C2-C3。这道题比较简单，可以一一列举，但是当街道数比较多的时候，一一列举就太麻烦了，中公教育专家带领大家从另外一个思路来求解。要想到达C3，必须先到B3或者C2，到B3之后直接往下走即可，到C2之后直接往右走即可，所以到达C3的最短路径条数就应该等于到达B3最短路径条数加到达C2最短路径条数。同理，想到达B3必须先到A3或者B2，所以 到达B3最短路径条数等于到A3最短路径条数加到B2最短路径条数。依次递推，得到下图：

注：每点所标数字为从A1点到达该点最短路径条数。

通过该图：我们可以发现每点所标数字都等于紧挨的上面点所标数字和紧挨的左面点所标数字和，这就是最短路径问题的规律，就像1+1=2那么简单。小伙伴，你会了吗?试试最开始的那道纵横各有7条街道的吧。

在考试的时候，如果命题人设置一些变化，考生应如何应对呢?中公教育专家建议各位考生不必慌，你只需分析清楚题干即可。比如：

【例】下图是一个街道的平面图，纵横各有6条路， 某人从最左上处的点(A)到最右下处的点B，中间有事必须过C点，共有多少条最短路线?

各位小伙伴，你想到怎么做了吗?中公教育专家提醒各位：既然必须过C点，我们只需先求出从A到C的最短路径条数，再求从B到C的最短路径条数即可。

  相关文章:

   2013年2月28日出入境边防检查总站面试真题作为一名出入境边检人员，领导让你负责开通一个网站与市民做交流活动，你会怎么做?【参考答案】开通边检交流网站，不仅可以为民众答疑解惑，也可以更好的进行边检知识的宣传，保证民众在日后的边检通关中能够

   【背景材料】今年4月以来，涉及65平方公里、94个自然村、3万多人的广州增城挂绿湖水利工程拆迁工作进展非常迅速。而部分拆迁户反映，政府用亲情逼迁，他们最终签了拆迁协议。而记者在调查中发现，增城市政府多个文件要求有关公职人员参与征拆工作。对于部分公职人员表现不积极，感到很大压力。不独广州增城，“亲情逼迁”在其他一些城市也出现过。此种拆迁行为的特点是，举凡拆迁对象的七大姑、八大姨，均有义务帮

   中公事业单位为帮助各位考生顺利通过事业单位招聘考试！今天为大家带来事业单位行政职业能力测试备考资料。希望可以帮助各位考生顺利备考！假言命题在事业单位考试中颇受考官青睐，根据掌握的历年真题来看几乎常常有假言命题的身影出现，所以说假言命题是大家备考事业单位考试时一定要掌握的重要考

   【导读】本篇内容中公事业单位提供面试热点知识《体育产业招商引资签约，六大项目成投资热点》。【热点梗概】近年来，杭州市积极调整体育产业结构，加大体育产业培育力度，体育产业门类逐渐增多。杭州市体育产业招商引资签约仪式从2015年开始，至今已持续四年，共签订有行业代表性的22家企业累计投资额突破110亿人民

   时事评论背景：政府购买服务，是政府改善公共服务供给质量、提高财政资金使用效率的有效手段。不久前，国家成立了政府购买服务改革工作领导小组，凸显了对政府购买服务的进一步重视，将对国家治理现代化和社会治理创新带来积极影响。时事评论观点：