niusouti.com
在图4-2中，由点O(0,0)到点P(5,6)的最短路径共有(39)条。图4-2 求最短路径A．126B．128C．252D．256
题目
在图4-2中，由点O(0,0)到点P(5,6)的最短路径共有(39)条。
图4-2 求最短路径
A．126
B．128
C．252
D．256
相似考题
参考答案和解析
正确答案：C
解析：图4-2中点O到点P的最短路径，即只能向上或向右走的所有路径。可以分两步来求从点O到点P的最短路径：1)从O到点(1，1)：共2条路径，分别是光向上和先向右走。2)从点(1，1)到点P：设向右走一格的长度为J，向上走一格的长度为y，那么不管怎么走，从点(1，1)出发，总是要经过4个x，5个y，方能到达点P，所以一条从点(1，1)到点P的最短路径对应一个由4个x、5个y共9个元素构成的排列；反之，给定一个这样的排列，按照x，y的含义，必对应一条从点(1，1)到点P的最短路径。故从点(1，1)到点P的最短路径计算转换为相异元素的全排列问题，其解为从排列的9个位置中选出4个位置放x，剩下的5个位置放y，计数结果为。按照乘法规则，从点O到点P的最短路径数为2×126=252条。
解析：图4-2中点O到点P的最短路径，即只能向上或向右走的所有路径。可以分两步来求从点O到点P的最短路径：1)从O到点(1，1)：共2条路径，分别是光向上和先向右走。2)从点(1，1)到点P：设向右走一格的长度为J，向上走一格的长度为y，那么不管怎么走，从点(1，1)出发，总是要经过4个x，5个y，方能到达点P，所以一条从点(1，1)到点P的最短路径对应一个由4个x、5个y共9个元素构成的排列；反之，给定一个这样的排列，按照x，y的含义，必对应一条从点(1，1)到点P的最短路径。故从点(1，1)到点P的最短路径计算转换为相异元素的全排列问题，其解为从排列的9个位置中选出4个位置放x，剩下的5个位置放y，计数结果为。按照乘法规则，从点O到点P的最短路径数为2×126=252条。
更多“ 在图4-2中，由点O(0,0)到点P(5,6)的最短路径共有(39)条。图4-2 求最短路径A．126B．128C．252D．256 ”相关问题
-
第1题：
下列关于Dijkstra算法的哪些说法正确
A．Dijkstra算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；
B．Dijkstra算法可用于求解无向图、有向图和混合图的最短路径问题；
C．Dijkstra算法的时间复杂度为O(n^2)，其中n为顶点数；
D．Dijkstra算法对边权无要求。
Dijkstra 算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；;Dijkstra 算法可用于求解无向图、有向图和混合图的最短路径问题；;Dijkstra 算法的时间复杂度为O(n ^2 )，其中n为顶点数 ； -
第2题：
3、如果加权图G中无负权，则最短路径的任意子路径都是最短路径。
正确 -
第3题：
下列关于Dijkstra算法的哪些说法正确
A．Dijkstra算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；
B．Dijkstra算法可用于求解无向图、有向图和混合图的最短路径问题；
C．Dijkstra算法的时间复杂度为O(n2)，其中n为顶点数；
D．Dijkstra算法对边权无要求。
对 -
第4题：
1、下列关于Dijkstra算法的哪些说法正确
A．Dijkstra算法是求加权图G中从某固定起点到其余各点最短路径的有效算法；
B．Dijkstra算法可用于求解无向图、有向图和混合图的最短路径问题；
C．Dijkstra算法的时间复杂度为O(n^2)，其中n为顶点数；
D．Dijkstra算法对边权无要求。
Dijkstra 算法能处理带负权值的图 -
第5题：
如果加权图G中无负权，则最短路径的任意子路径都是最短路径。
正确