湖南公务员考试2014年湖南公务员考试行测排列组合之最短路径

湖南公务员考试行测的一种题型是排列组合问题，因为排列组合问题不仅可以自身单独出题，还可以结合概率相关的知识进行出题。纵观湖南省公务员考试历年真题我们发现，在湖南省考中有一种题型，在国考及其他省考中从未出现过的一种出题方式，那就是最短路径问题。中公教育老师在此将这种题型进行深入分析。

什么是最短路径呢?顾名思义，从一个地点到达另一个地点，路径要求最短，问的是这时候方法总数是多少，也就是说最短路径不只是一条也不是一种走法，这种题型应该怎么来解题呢?我们通过一道例题来看一下这类题的解法。

例1：某城市街区由16个矩形组成，如图所示，其中实线表示马路，如果只能在马路上行走，那么从A点到B点的最短路径有多少条?

解析：看到这种题目，大部分人的做法就是开始各种数，各种算，发现根本数不清楚到底多少，这时候怎么做呢?那我们可以来看一下，要想从A点到达B点应该怎么做，从A到到B肯定要向左走，也要向上走，走法挺多，但是题目中既然问的是最短路径，肯定要数最短路径的数量，肯定不能往回走，那么既然这么限制了，那么就意味着向上至少要走4步，向左也要走4步，也就是说最短路径肯定是要走8步，而且必须左4步，上4步，区别就是哪4步向上走哪4步向右走，只要选定了4步向右走或者向上走，那么另外的4步走法就已经确定了，选法不同也就是意味着走法不同，题目瞬间转化为8步里面任意选出4步向上走，就转化为一个组合问题，8个里面任意选4个的方法数是

这种问最短路径的题目，就是首先要确定到底怎么走法是最短的，一般都是要两个能够去走，两个方向分别走多少，然后总的步数就已经确定了，然后就是从总的方法数里面挑选其中一个方向的走法，也就转化为了一个普通的排列组合问题，解题就变的非常容易了。接下来我们来看一下上海公务员考试的一道真题。

例2：如图所示，某城镇共有6条东西方向的街道和6条南北方向的街道，其中有一个湖，街道在此变成一个菱形的环湖大道。现在要从城镇的A处送一份加急信件到B处，为节省时间，要选择最短的路线，共有( )种不同走法。【2010-上海】