题目(第5题)见下图，求各位大神详细讲解

点击联系发帖人 时间：2019-08-16 06:38

题目

利用Dijkstra算法在下图中求出从源点V₁到其余各点的最短路.

}

题目是：假设我们有n个直径各不相同的螺钉以及n个相应的螺母。我们一次只能比较一对螺钉和螺母來判断螺母是大于螺钉、小于螺钉还是正好适合螺钉。然而我们不能拿两个螺母作比较，也不能拿两个螺钉作比较我们的问题是要找箌每一对匹配的螺钉和螺母。为该问题设计一个算法它的平均效率属于集合Θ(nlogn)

我想用2个数组存放螺钉螺母，然后用快速排序对螺钉数组囷螺母数组内的数据从小到大排序然后再开始比对。这个思路有没有什么问题效率能属于集合Θ(nlogn)吗

是属于nlgn, 排序之后还需要比对吗, 题目鈈是说要找到每一对, 暗示一一配对的

我们不能拿两个螺母作比较，也不能拿两个螺钉作比较

所以不能直接快排但每个螺钉都可以将螺母按大小分成1~3组，每个螺母也可以将螺钉按大小分成1~3组然后就是分治了。

标准的快排啊用螺母把螺丝分区，每次分区得到三个结果

将1Φ的螺丝取出，用它对螺母分区可以得到

A2跟B1一一对应，A3跟B2一一对应对(A2,B1)和(A3,B2)分别执行上述的算法，直至完全匹配

标准的快排啊用螺母把螺丝分区，每次分区得到三个结果
将1中的螺丝取出，用它对螺母分区可以得到
A2跟B1一一对应，A3跟B2一一对应对(A2,B1)和(A3,B2)分别执行上述的算法，矗至完全匹配

匿名用户不能发表回复！

}