2015年公务员考试行测冲刺阶段技巧：1+1解决“最短路径问题”

　　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最短路径条数。依次递推，得到下图：