1125人阅读
编程马拉松（27）
1 题目描述
　　小世界现象（又称小世界效应），也称六度分隔理论（英文：Six Degrees of Separation）。
　　假设世界上所有互不相识的人只需要很少中间人就能建立起联系。后来1967年哈佛大学的心理学教授斯坦利·米尔格拉姆根据这概念做过一次连锁信实验，尝试证明平均只需要5个中间人就可以联系任何两个互不相识的美国人。
　　NowCoder最近获得了社交网站Footbook的好友关系资料，请你帮忙分析一下某两个用户之间至
　　少需要几个中间人才能建立联系？
1.1 输入描述:
　　输入第一行是一个整数t，表示紧接着有t组数据。
　　每组数据包含两部分：第一部分是好友关系资料；第二部分是待分析的用户数据。
　　好友资料部分第一行包含一个整数n (5≤n≤50)，表示有n个用户，用户id用1-&n表示。
　　紧接着是一个只包含0和1的n×n矩阵，其中第y行第x列的值表示id是y的用户是否是id为x的用户的好友（1代表是，0代表不是）。假设好友关系是相互的，即A是B的好友意味着B也是A的好友。
　　待分析的用户数据第一行包含一个整数m，紧接着有m行用户组数据。
　　每组有两个用户ID，A和B (1≤A, B≤n; A != B)。
1.2 输出描述:
　　对于每组待分析的用户，输出用户A至少需要通过几个中间人才能认识用户B。
　　如果A无论如何也无法认识B，输出“Sorry”。
1.3 输入例子:
1 1 0 0 1 0
1 1 0 1 0 1
0 0 1 0 0 1
0 1 0 1 0 1
1 0 0 0 1 0
0 1 1 1 0 1
1.4 输出例子:
2 解题思路
　　题目要求某两个人之间最少通过多少个中间人才能建立联系，人与人之间的关系用一个图进行表示，有直接关系的使用1表示，没有关系的使用0表示。可以对这个关系矩阵进行改进，将自身与身的关系计为1，&v,w&存在直接关系记为1，不存在直接关系的记为+∞。要求，&x,y&最少通过多少个中间人可以取得联系，可以先计算，&x,y&之间的最短路径，因为边的权权重都是1，所以最短路径就是，&x,y&所经过的最少的边的数目e，而，&x,y&最少的联系人数目就是，&x,y&最少边所在线段中间的顶点数，即e-1。
　　经过分析可以得，该题可以通过Dijkstra、Bellman-Ford或者Floyd算法进行处理。本题分析过程讲解Floyd。Dijkstra方法见算法实现。
2.1 Floyd算法
　　问题的提出：已知一个有向网（或无向网），对每一对顶点vi≠vj，要求求出vi与vj之间的最短路径和最短路径长度。
解决该问题的方法有：
轮流以每个顶点为源点，重复执行Dijkstra算法（或Bellman-Ford算法）n次，就可求出每一对顶点之间的最短路径和最短路径长度，总的时间复杂度是O(n3)（或O(n2+ne)）。
采用Floyd（弗洛伊德）算法。Floyd 算法的时间复杂度也是O(n3)，但Floyd算法形式更直接。
2.2 算法思想
　　Floyd（弗洛伊德）算法的基本思想是：对一个顶点个数为n的有向网（或无向网），设置一个n×n的方阵A(k)，其中除对角线的矩阵元素都等于0外，其他元素A(k)[i][j](i≠j)表示从顶点vi到顶点vj的有向路径长度，k表示运算步骤，k=-1、0、1、2、…、n-1。
　　初始时：A(-1)= Edge（图的邻接矩阵），即初始时，以任意两个顶点之间的直接有向边的权值作为最短路径长度：
　　　　1)　对于任意两个顶点vi和vj，若它们之间存在有向边，则以此边上的权值作为它们之间的最短路径长度；
　　　　2)　若它们之间不存在有向边，则以MAX作为它们之间的最短路径。
　　以后逐步尝试在原路径中加入其他顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的最短路径长度减少了，则以此新路径代替原路径，修改矩阵元素，更新为新的更短的路径长度。
　　例如，在图1所示的有向网中，初始时，从顶点v2到顶点v1的最短路径距离为直接有向边&v2,v1&上的权值(=5)。加入中间顶点v0之后，边&v2,v0&和&v0,v1&上的权值之和(=4)小于原来的最短路径长度，则以此新路径&v2,v0,v1&的长度作为从顶点v2到顶点v1的最短路径距离A[2][1]。
　　图1 Floyd算法：有向网及其邻接矩阵
　　将v0作为中间顶点可能还会改变其他顶点之间的距离。例如，路径&v2,v0,v3&的长度(=7)小于原来的直接有向边&v2,v3&上的权值(=8)，矩阵元素A[2][3]也要修改。
　　在下一步中又增加顶点v1作为中间顶点，对于图中的每一条有向边&vi,vj&，要比较从vi到v1的最短路径长度加上从v1到vj的最短路径长度是否小于原来从vi到vj的最短路径长度，即判断A[i][1]+A[1][j]& A[i][j]是否成立。如果成立，则需要用A[i][1]+A[1][j]的值代替A[i][j]的值。这时，从vi到v1的最短路径长度，以及从v1到vj的最短路径长度已经由于v0作为中间顶点而修改过了，所以最新的A[i][j]实际上是包含了顶点vi,v0, v1, vj的路径的长度。
　　如图1所示，A[2][3]在引入中间顶点v0后，其值减为7，再引入中间顶点v1后，其值又减到6。当然，有时加入中间顶点后的路径较原路径更长，这时就维持原来相应的矩阵元素的值不变。依此类推，可得到Floyd算法。
　　Floyd算法的描述如下。
　　定义一个n阶方阵序列：A(-1),A(0),A(1), …,A(n-1)，其中：
　　A(-1)[i][j]表示顶点vi到顶点vj的直接边的长度，A(-1) 就是邻接矩阵Edge[n][n]。
　　A(0)[i][j]表示从顶点vi 到顶点vj，中间顶点（如果有，则）是v0 的最短路径长度。
　　A(1)[i][j]表示从顶点vi 到顶点vj，中间顶点序号不大于1 的最短路径长度。
　　A(k)[i][j]表示从顶点vi 到顶点vj 的，中间顶点序号不大于k的最短路径长度。
　　A(n-1)[i][j]是最终求得的从顶点vi 到顶点vj的最短路径长度。
　　采用递推方式计算A(k)[i][j]：
　　增加顶点vk作为中间顶点后，对于图中的每一对顶点vi和vj，要比较从vi到vk的最短路径长度加上从vk到vj的最短路径长度是否小于原来从vi到vj的最短路径长度，即比较A(k-1)[i][k]+A(k-1)[k][j]与A(k-1)[i][j]的大小，取较小者作为的A(k)[i][j]值。
　　因此，Floyd 算法的递推公式为：
A(k)[i][j]=???Edge[i][j]min{A(k-1)[i][j],A(k-1)[i][k]+A(k-1)[k][j]}k=-1k=0,1,2,…,n-1
2.3 算法实现
　　Floyd 算法在实现时，需要使用两个数组：
数组A：使用同一个数组A[i][j]来存放一系列的A(k)[i][j]，其中k=-1,0,1,…, n-1。初始时，A[i][j]=Edge[i][j]，算法结束时A[i][j]中存放的是从顶点vi到顶点vj的最短路径长度。
path数组：path[i][j]是从顶点vi到顶点vj的最短路径上顶点j 的前一顶点的序号。
Floyd算法具体实现代码详见例2.1。
　　例2.1　利用Floyd算法求图1(a)中各顶点间的最短路径长度，并输出对应的最短路径。
　　假设数据输入时采用如下的格式进行输入：首先输入顶点个数n，然后输入每条边的数据。每条边的数据格式为：u v w，分别表示这条边的起点、终点和边上的权值。顶点序号从0 开始计起。最后一行为-1 -1 -1，表示输入数据的结束。
　　分析：
　　如图2所示，初始时，数组A实际上就是邻接矩阵。path数组的初始值：如果顶点vi到顶点vj有直接路径，则path[i][j]初始为i；如果顶点vi到顶点vj没有直接路径，则path[i][j]初始为-1。在Floyd 算法执行过程中，数组A 和path各元素值的变化如图2所示。在该图中，如果数组元素的值有变化，则用粗体、下划线标明。
　　以从A(-1)推导到A(0)解释A(k)的推导。从A(-1)推导到A(0)，实际上是将v0作为中间顶点。引入中间顶点v0后，因为A(-1)[2][0]+A(-1)[0][1]=4，小于A(-1)[2][1]，所以要将A(0)[2][1]修改成A(-1)[2][0]+A(-1)[0][1]，为4；同样A(0)[2][3]的值也要更新成7。
　　当Floyd算法运算完毕，如何根据path 数组确定顶点vi到顶点vj的最短路径？方法与Dijkstra算法和Bellman-Ford算法类似。以顶点v1到顶点v0的最短路径加以解释。如图2所示，从path(3)[1][0]=2可知，最短路径上v0的前一个顶点是v2；从path(3)[1][2]=3可知，最短路径上v2的前一个顶点是v3；从path(3)[1][3]=1可知，最短路径上v3的前一个顶点是v1，就是最短路径的起点；因此，从顶点1到顶点0的最短路径为：v1→v3→v2→v0，最短路径长度为A[1][0]=11。
3 算法实现
import java.util.ArrayL
import java.util.LinkedL
import java.util.L
import java.util.S
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int group = scanner.nextInt();
for (int i = 0; i & group; i++) {
int n = scanner.nextInt();
int[][] edge = new int[n][n];
for (int j = 0; j & j++) {
edge[j] = new int[n];
for (int k = 0; k & k++) {
edge[j][k] = scanner.nextInt();
int m = scanner.nextInt();
List&Integer& pairs = new ArrayList&&(m * 2);
for (int j = 0; j & j++) {
pairs.add(scanner.nextInt() - 1);
for (int j = 0; j & j++) {
for (int k = 0; k & k++) {
if (j == k) {
edge[j][k] = 0;
} else if (edge[j][k] == 0) {
edge[j][k] = Integer.MAX_VALUE;
List&Integer& result = floyd(edge, pairs);
for (Integer r : result) {
if (r & Integer.MAX_VALUE) {
System.out.println(r - 1);
System.out.println("Sorry");
scanner.close();
private static List&Integer& floyd(int[][] edge, List&Integer& pairs) {
int MAX = Integer.MAX_VALUE;
int N = edge.
int[][] A = new int[N][N];
int[][] path = new int[N][N];
for (int i = 0; i & N; i++) {
A[i] = new int[N];
path[i] = new int[N];
for (int j = 0; j & N; j++) {
A[i][j] = edge[i][j];
if (i != j && A[i][j] & MAX) {
path[i][j] =
path[i][j] = -1;
for (int k = 0; k & N; k++) {
for (int i = 0; i & N; i++) {
for (int j = 0; j & N; j++) {
if (k == i || k == j) {
if (A[i][k] & MAX && A[k][j] & MAX && A[i][k] + A[k][j] & A[i][j]) {
A[i][j] = A[i][k] + A[k][j];
path[i][j] = path[k][j];
List&Integer& result = new LinkedList&&();
while (!pairs.isEmpty()) {
int x = pairs.remove(0);
int y = pairs.remove(0);
result.add(A[x][y]);
private static List&Integer& dijkstra(int[][] edge, List&Integer& pairs) {
int N = edge.
int MAX = Integer.MAX_VALUE;
boolean[] S = new boolean[N];
int[][] DIST = new int[N][N];
int[][] PREV = new int[N][N];
List&Integer& result = new ArrayList&&();
for (int v = 0; v & N; v++) {
DIST[v] = new int[N];
PREV[v] = new int[N];
for (int i = 0; i & N; i++) {
S[i] = false;
DIST[v][i] = edge[v][i];
if (DIST[v][i] == MAX) {
PREV[v][i] = -1;
PREV[v][i] = 0;
S[v] = true;
for (int i = 1; i & N; i++) {
int min = MAX;
int u = 0;
for (int j = 0; j & N; j++) {
if (!S[j] && DIST[v][j] & min) {
min = DIST[v][j];
S[u] = true;
for (int j = 0; j & N; j++) {
if (!S[j] && edge[u][j] & MAX) {
int weight = DIST[v][u] + edge[u][j];
if (DIST[v][u] & MAX && edge[u][j] & MAX && weight & DIST[v][j]) {
DIST[v][j] =
PREV[v][j] =
for (int i = 0; i & pairs.size(); i += 2) {
int v = pairs.get(i);
int w = pairs.get(i + 1);
result.add(DIST[v][w]);
private static void print(int[][] arr) {
for (int[] line : arr) {
print(line);
private static void print(int[] arr) {
for (int val : arr) {
if (val != Integer.MAX_VALUE) {
System.out.print(val + " ");
System.out.print("- ");
System.out.println();
4 测试结果
5 其它信息
因为markddow不好编辑，因此将文档的图片上传以供阅读。Pdf和Word文档可以在Github上进行。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：441728次
积分：9358
积分：9358
排名：第1356名
原创：435篇
评论：148条
文章：28篇
阅读：22922
文章：105篇
阅读：102544
文章：12篇
阅读：7769
阅读：7816
文章：126篇
阅读：139972
文章：24篇
阅读：34857
文章：65篇
阅读：73313有2个o连在一起的英语单词_百度知道