Skip to main content

第一章概论

问题:人狼羊菜问题还能有哪些模型?

王子祎答:还可以用宽搜模型,初始状态原岸边为二进制0000,最终状态为二进制1111.通过队列实现最短路径的求得。

第二章 线性表

问题:若入栈的顺序为1,2,3,4那么出栈的顺序可以有哪些?

高飙答:1234 1243 1324 1342 1432 2134 2143 2314 2341 2431 3214 3241 3421 4321

问题:顺序表中,插入删除操作需要考虑哪些问题

王子祎答:插入时要考虑表中元素是否已满,满了的话需要重新申请空间并且复制;删除时要考虑表是否为空;插入删除均需考虑其余元素的平移问题。

问题:顺序表和链表的选择

王子祎答:结点变化的动态性角度:若经常需要插入删除结点,则链表好于顺序表;若指针字节占总字节比例过大或者存储密度过大,则最好用顺序表。

第三章 栈与队列

问题:请总结前缀表达式的性质,以及求值过程。

吴鹏答:我觉得需要用到递归求解,因为前缀表达式是表达式树的前序遍历结果,因此要求出当前值就需要进入递归下一层才能得到需要的数值。求值过程就是当前值等于左子树返回值和右子树返回值经过当前操作符运算得到新值。

王子祎答:顺序读入符号序列,若遇到符号,则压栈;将遇到的第一个操作数也压栈;若下一个仍然是操作数,则将此连续的两个操作数出栈,再出栈运算符,将运算结果入栈。若遇到等号,栈内唯一的元素出栈,此为结果。

郭秭含答:可以将前缀表达式逆序后就得到后缀表达式,按照后缀表达式的方式来求解,这是我所不知道的,学到了新的方法。

问题:栈往往用单链表实现。可以用双链表吗?哪个更好?

高飙答:栈用单链表实现更好。双链表记录了2个方向的元素,而栈是单端操作的,所以双链表记录了很多多余的信息,会导致空间浪费,没有必要。

王子祎答:单链表实现更好。因为双链表中指针占的存储区域更大,同时插入删除的操作也更繁琐。而且,作为栈,我们主要的操作是得到其下一个元素,很少用到向上的指针,因此双链表意义也并不大。所以我认为用单链表实现好。

谢毅泽答:单链表更好,因为栈的功能没有用到第二条链(从栈底到栈顶),浪费了结构性存储空间。

问题:链式队列往往用单链表。为什么不用双链表来实现?

李芊答:用单链表是因为队列本来就只能在尾部插入在头部读取,不需要在中间遍历,所以用单链表既能满足需求又比较简单高效。双链表没有优势还浪费存储空间。所以不用双链表来实现。

王子祎答:首先,双链表会消耗更多存储空间存指针。其次,队列具有FIFO的性质,当我们查看其中一个元素时,上一个元素已经出队了。所以我们并不需要一个向前的指针来指向该元素之前的元素。

问题:如何让循环队列不浪费一个空间?

刘家霖答:在外部设置一个监视变量记录队列内元素个数,这样子避免了队空与队满同个标志。

问题:从初始输入序列12,…,n,希望利用一个栈得到输出序列P1P2,…,Pn (它们是1 2,…,n的一种排列)。若存在下标ijk,满足i<j<k 同时 Pj<Pk<Pi,则输出序列是否合法?

王子祎答:输出序列不合法。因为输出序列必须满足如下性质:即在编号K的数据出栈之后,之后出栈且编号比K小的的数据必须按编号从大到小依次出栈。因为若K出栈时,比它小的I,J均在栈中,则必然是I先入栈,J再入栈,故肯定JI先出栈。即输出序列不合法。

问题:STL为什么将top() pop()分开,而不提供ptop()

王子祎答:因为将其分开可以使函数在概念上更明确,方便用户使用。同时降低了函数的耦合程度。第三点便是提高了程序运行效率,因为若是ptop(),则必须返回值而不是引用(因为原数据空间已释放),所以效率会变低。

问题:只用front rear,长度为n的队列,最大可容纳多少元素?

王子祎答:最大容纳n-1个。因为当队列空时front=rear,当容纳n个元素时也有front=rear。因此当容纳n个元素时无法判断队列的空与满,所以最大容纳n-1个元素。

问题:若采用虚指方法实现队尾指针(rear指向队尾元素后一个元素,和实指相比后移一位),在具体实现上有何异同?哪一种更好?

郑子威答:

具体实现差别在于一个是判断空与满的不同,另一个是插入新节点与rear后移语句顺序的不同。实指针先后移,然后添加新节点,虚指针反之。实指针的判断空与满的判断分别为((rear+1)%n==front)((rear+2)%n==front),虚指针的判断分别为(rear==front)((rear+1)%n==front)。两者相比较之下,一方面虚指针的代码更为简洁,另一方面,少一个模运算,能够节省算法时间。(模运算耗时较大),但是就理解上,实指针更为直观。

第四章 字符串

问题:String类的对象大小(size)为多少?

邹良川答:下课后在网上查找相关内容发现,string类型的sizeof()返回值是不确定的,与编译器相关,4是最常见的一种返回值。

问题:String抽取子串需要注意的地方?

高飙补答: s2 = s1.substr(start, len),需要注意start+len不能超过s1字符串的末尾。如果超过,会取子串到s1末尾为止。

问题:设计一个算法来实现字符串逆序存储,要求不另设串存储空间

高飙补答:1、用异或操作可以交换两个元素,如a,b交换:a = a ^ b; b = a ^ b; a = a ^ b; 通过异或的方法可以不开辟额外空间将字符串逆序存 储,只要将首尾对称的位置字符交换即可。2、可以用字符串的截止标记\0位置作为临时交换的空间,将字符串逆序后,重置\0也可以达到同样的目的。

问题:为什么每次kmp算法匹配不成功要找next[j]而不是j+1或者j-1

郭秭含答:因为每次要保证所枚举位置和当前串的后缀相同,且要保证最大。首先找next可以保证后缀相同,而且由next的定义也可以保证每次都最大。

问题:KMP的时间复杂度

郭秭含答:KMP的时间复杂度是线性的 。母串的移动是线性的。子串只有走到当前位置才能回退,所以至多是两倍母串长度,也是线性的。

问题:Trie的时间复杂度

郭秭含答:当建好Trie树后,寻找next数组和匹配都是线性的,整个过程都和KMP类似。

如果每个节点用26位存储子节点,建树也是线性的。

问题:前缀中的周期,len%(len-next[len])==0表示存在循环节的正确性。

刘家霖答:len%(len-next[len])=0,故可以将整个字符串分割为等长的w(w= len/(len-next[len])),每段长为l,定义p[i]为第i段字符串, 根据next数组的定义有p[1]=p[2],p[2]=p[3]……p[w-1]=p[w],所以每段都是相同的。

问题:s.substr(x,y)的作用是什么?需要注意什么?

王天明答:从s串的x位置开始复制y位。当x+y超过串长后复制到字符串结束为止。

问题:如何求字符串s的最小循环节?

王天明答:对串s求其的next数组,再从s的最后一位沿next数组向前退,若能返回到开头即存在循环节且n-next[n]为最小循环节。

问题:优化后的next数组对匹配有优化作用吗?

王天明答:当模式串数量很大,总长远超待匹配串时,优化有明显作用。

问题:对于一个有n个字符的串,其一共有多少子串

王子祎答:对于一个有N个字符的串,其子串可以由1,2n个字符组成,分别有n, n-11种。外加一个空串,因此共1+1+2+3..+n = 1 + n(n-1)/2种。

问:设 S1, S2 为串,请给出使 S1+S2 == S2+S1 成立的所有可能的条件(其中 + 为连接运算)

王子祎答:s1s2至少一个为空;或者s1==s2;或者s1s2分别为一个前缀的若干倍。

问题:next[i]的计算方法:

        如果i==0 next[i]=-1;

        如果i>0,假设next[i-1]=k.

        如果P[i-1]==P[k] next[i]=k+1;

        否则,如果k==0      next[i]=0;

        否则 k=next[k],进行循环.

   为何是next[k] ?

王子祎答:此处用递归实现,因为p[i-1] != p[k],所以之前的前缀没有和当前后缀匹配上,递归next[k]为能匹配上当前前缀的前缀,因此也能在最后一位前匹配上当前后缀,因此可以继续比较

问题:next数组有两种定义方式,分别如下所示:

next数组的第二种定义方法有何优劣?

谢毅泽答:可以方便地求出最后一个元素之后位置(假装那里有元素)的前缀指针,以达到计数的目的。(当然不这么定义也可以,这样方便一点)

问:kmp算法计算next数组时i==0时,next[i]=0-1的区别。

吴先答:如果next[0]=-1,那么相当于在模式串的开头-1处有一个任意字符,可以让目标串和模式串指针无条件向后移动一位。

郑子威问:Rabin-Karp的算法本质是什么?

郑子威答:

RK算法是将字符串看做是数组,通过数值对比来代替效率较低的朴素字符串匹配。直接将模式串通过进制转换与取摸,映射成一个数字,然后对目标串的每一位所代表的的字符串进行匹配。匹配就是将目标串中当前位往后与模式串等长的字符串映射成数字,对比两个数字。

如果匹配成功,进行一次朴素对比判断是否伪匹配;然后将目标串的数字去掉最高位(即匹配起点的字符所代表的的数字)后再乘进制数加上下一位字符的数值。

       因此实质上RK算法是通过对字符进行hash,并运用数值对比的高效率来对两个串的hash值进行对比。由于采用进制数对字符串进行hash,从而使相邻两个串的hash值可以O(1)的快速相互得出。因此该方法可以进行多串匹配。期望复杂度为O(n),最差会退化到O((n-m+1)m)。

       我认为RK算法的优点在于比较好写也较好理解,在匹配成功的情况较少的时候会有不错的效果。

郑子威问:Shirt-OR算法本质是什么?

郑子威答:

Shirt-Or是一个非常巧妙运用位运算的字符串匹配算法,他要求模式串的长度不能超过计算机字长(32或者64),算法复杂度为O(n)n表示目标串的长度。复杂度比KMP还低,而且由于位运算的效率高,算法的实际效率极高。

       具体操作室用一个整数M表示当前匹配的进度,二进制上若第i位为0表示当前存在一个串匹配到第i位。

       预处理是对于模式串中的每一种字符,用一个整数X[j]表示字符j在模式串中的出现情况。若第i位为0,表示模式串中第i位为该字符。

       具体操作是,M初始化为-1,即每一位都是1

1  如果当前M最高位(算法描述中的最高位都是表示位数等于模式串的长度的那一位)为0,表示当前位匹配成功。

2  M<<=1M = M | X[j] (j表示下一位的字符)

算法描述相当简洁,写起来也很好写,想法就是利用位运算,通过X[j]M中每一个匹配状态进行筛选,若第i位仍为0,代表该字串通过字符j的筛选,即第i位确实为j

郑子威问:Boyer-Moore算法本质是什么?

郑子威答:

       BM算法是一个通过两个后缀匹配优化规则来实现快速跳转的字符串匹配算法,最好的复杂度为O(n/m),最坏的复杂度为O(n),在实际中往往具有比KMP更高的效率。

       大致的算法思路是通过模式串与目标串的后缀比较,运用两个规则进行优化,一个称之为坏字符规则,一个称之为好后缀规则。

       坏字符规则,记录模式串中每一种字符i,用delta1(i)表示模式串中右边的该字符距离右端有多远,如果没有出现则为模式串长度。那么对于当前匹配,如果失配的话,根据坏字符规则,模式串位置可以右移delta1(s[i])个位置(i为目标串匹配中当前位)。

       好后缀规则,该规则有点类似KMP中的next数组的作用,但是不同的是,该规则记录的是当前已经匹配的后缀,在模式串当前匹配位往前,能够“重现”该后缀的最大位置,如果不能“重现”,则记录的是模式串前缀能与该后缀的后缀能匹配的最大位置,记为delta2。那么显然如果当前失配,就可以将模式串往后跳转至delta2与目标串当前位对齐。对于如何求delta2,只需要对模式串的逆序求KMPnext即可。那么对于一次失配,模式串后跳就取决于delta1delta2两种跳转规则的跳转较大者。

       因此实质上,BM算法可以算是利用KMP与坏字符规则进行优化的匹配算法。

详细算法讲解可以参考

http://blog.csdn.net/iJuliet/article/details/4200771

http://blog.chinaunix.net/uid-23390992-id-3320412.html

第五章 二叉树

问题:怎么建立一个常数时间内得到最大和最小值的数据结构。

李芊答:可以用最大最小堆。最小最大堆是一棵完全二叉树,且其中每个元素有一个key数据成员。树的各层交替为最小层和最大层。根结点在最小层。设x是最小最大堆的任意结点。若x在最小(最大)层上,则x中的元素的key值在以x为根的子树的所有元素中是最小(最大)的。位于最小(最大)层的结点称为最小(最大)结点。

问题:前、中、后序哪几种结合可以恢复二叉树的结构?

杜若谷答:中-前序列组合、中-后序列组合均可。前-后组合不可。

问题:二叉树终端结点数n0,度为2的结点数为n2,证明有n0=n2+1

郭秭含答:考虑树上三种结点n0,n1,n2n0有两个空子树,n11个空子树,n2没有空子树。空子树的数量=n1产生的空子树+n2产生的空子树=n1+2*n0=n1+n0+n2+1=n+1

李芊答:主要思路:以结点总数n为桥梁联立两个等式:

n = n0 + n1 + n2n = n1 + 2*n2 + 1。所以n0 = n2 + 1

问题:宽搜与前序遍历的非递归算法对比。

李芊答:他们的共同点就是访问一个结点直接读取数据。宽搜利用的是队列,先进先出,每次从头读取一个结点并把非空左、右子结点放入队列尾部。而前序遍历利用的是栈存储结点指向右子树的指针,不用保存当前访问的结点。

问题:当外部结点的数目不能构成满bHuffman树时,需附加多少个权为0的“虚”结点?

李芊答:设有r个外部结点的b叉树。可以设总结点数目为n,如果是满b叉树的话,只有叶子节点n0与子结点数目为bnb两种结点。即n=n0+nb。那么除了根结点之外每个结点都是由父结点连接过来的,所以又可以知道n = b * nb + 1。联立两个式子可以得到n0=(b-1)*nb+1

而如果不需要加虚结点,那么n0 = r,也就有r = (b-1) * nb + 1,可以推出(r-1)%(b-1)==0。否则就需要加上n’个虚结点,那么n0 = n + r = (b-1) * nb + 1。也就得到(n+ r1)%(b-1) == 0

所以可以得到n'=b1-(r-1)%(b-1)即为所求。

问题:扩充二叉树和满二叉树的关系

李祝祺答:扩充二叉树一定是满二叉树,满二叉树不一定能有其它的二叉树扩充而来

问题:怎样使二叉树的前序遍历不丢失信息

李祝祺答:补全空结点,使其变成一棵满二叉树

问题:二叉树找到父结点后找兄弟结点的方法

李祝祺答:找到父结点后,如果父结点的左子结点是该结点本身,则返回父结点的右子结点。否则,返回父结点的左子结点

问题:二叉树遍历的时空复杂度分析

王皓答:时间:O(n),因为每个节点都只被访问常数次

空间:O(n),考虑不用循环队列的情况,就要存储所有结点,故最坏需要 O(n)

问题:完全三叉树的下标公式

王皓答:若下标从1开始,i 的三个子结点分别为 3i - 1, 3i, 3i + 1i 的父节点为 (i + 1) /3

问题:堆在向下筛选SiftDown操作时,若一旦发现逆序对,就交换会怎么样?

王皓答:会做许多无用的交换,升高复杂度常数。

问题:出栈序列统计简单的方法?

王天明回答: P2n为这样所得的数的个数。在2n位上填入n1的方案数为 Cn 2n)。再计算不符条件的方案数。不合要求的数的特征是从左而右扫描时,必然在某一奇数2m+1位上首先出现m+10的累计数,和m1的累计数。在将2m+1位后的01挑换,即得到一个n+10n-11的序列。这样每一个不符合条件的序列对应一个n+10 n-11的序列。所以不符合的总数是Cn+1 2n)。所以答案是C(n 2n)-C(n+1 2n).

问题:为何前序遍历+后序遍历无法还原出一棵二叉树?

王子祎答:首先,将树映射为遍历序列会导致信息的缺失。比如,某棵树中的空子树并不会体现出来。同时,每种遍历序列所蕴含的信息也是不同的,前序后序序列可以告诉我们关于根的信息;当有根的信息后,中序序列可以告诉我们哪些结点在左子树,哪些在右子树。因此,我们需要多个遍历序列共同去得到需要的全部信息。而前序+后序序列中,我们更多的只是得到了根的信息,而且含有大量冗余,而且有些信息无法得到,比如中序序列可以提供的结点的左右位置。因此前后序列是不足以完全恢复二叉树的。

问题:后序框架是否支持前序、中序访问?若支持,如何改动?

王子祎答:后序框架支持前序、中序访问,可以通过改变visit语句的位置来实现。改为前序遍历时,改为在压栈时访问结点。当支持中序访问时,改为从栈中取出,再次压栈前访问结点。

问题:后序遍历时,栈中结点有何规律?栈中存放了什么?

王子祎答:后序遍历时总是放着本节点到根的祖先轨迹,栈中存放了需要访问的线索。

问题:如何防止二叉搜索树退化成链。

吴先答:尽量保持每个树根的两颗子树的高度相等或相差一,对于不满足这个条件的树根进行操作以使其在满足二叉搜索树定义的条件下尽量满足这个平衡条件。

问题:若二叉搜索树中含有重复的元素,如何进行元素的插入和删除操作?

许瑞琦答:可以在每个节点增设一个标记位,标记当前该节点元素的个数。若要插入/删除的元素BST中已存在,则只需修改标记位的值即可。

(张老师补充:实际情况中往往在该节点建立一个链表,动态存储相同key值的元素)

问题:二叉树的计数与出栈序列的方案数是一样的,那么有没有一种映射方法,能将结点数为n的每一种二叉树与n个元素顺序入栈的出栈序列形成一个双射?

郑子威答:

首先,我们知道,对于任意的一种前序遍历序列,都可以通过定义不同结点的编号,来对应到每一种形态的二叉树。也就是说,任意一种前序遍历,可以由每一种形态的二叉树得出。因此,对于1,2..,n的前序遍历,可以是n个结点的任意形态二叉树。又因为前序加中序遍历可以确定唯一的一颗二叉树,因此任意一种形态的二叉树,根据前序遍历编号后,对应着唯一的一个中序遍历。这时候可以发现,中序周游的进出栈顺序就正好对应着Catalan 0-1序列,从而对应一个出栈序列。

原因:因为前序遍历为1..n,所以进栈顺便必然为1..n,但是因为是中序,只要栈不为空,可以任意出栈(意味着剩下未入栈结点属于右子树或者到根节点路径上的某棵右子树),正好对应所有的Catalan 0-1序列。

因此,映射方法为,对于任意一颗二叉树,编号使其前序遍历为1..n,然后对其进行中序遍历得到Catalan 0-1序列,从而映射到一个出栈序列。

问题:在仅有parent指针的情况下,找父节点可以用BFS实现吗?

邹良川答:可以。因为之前用DFS实现了找父节点的算法,而算法中遍历顺序并不重要,BFS也能实现同样的效果。

第六章 树和森林

问题:森林的非递归深搜框架?

杜若谷答:和二叉树前序遍历框架类似,向左下循环同时将右孩子压入栈内。

问题:如何删除一个以root为根的子树,需要注意什么?

吴先答:从root开始对root的所有孩子递归进行删除,访问到叶子结点时直接释放叶子节点内存即可。要注意删除时对空指针的判断,防止出现内存错误。

问题:并查集编程题目中如果除了说明两个节点为朋友关系外,还给出两个节点为敌对关系(敌人的敌人就是朋友),此时该如何进行操作?

罗浩然答:对于每个节点x,不光记录father[x],也就是它的父节点,同时记录relation[x],即它与父子节点之间的关系.每次进行合并的时候,只需要改动其中一个relation,把其变为与现在的父亲节点的关系,在进行find的路径压缩的时,同时更新这条路径上所有点的relation,使其变为与现在真正的根节点的关系.

问题:下面的算法是否能遍历森林?

template<classT>

voidTraverse(TreeNode<T> *rt) {

 if (rt == NULL)

 return;

Visit(rt);

TreeNode* temp = rt->LeftMostChild();

 while (temp != NULL) {

    Traverse(temp);

    temp = temp->RightSibling();

}

}

赵若远回答:不能,这种算法只能遍历森林的第一颗树。

问题:如何求动态表示法下树结点的左子右兄

李祝祺答:找到结点的leftmostchild就是其左子,找到其父结点,然后再根据其父结点找到其后面的第一个结点就是其右兄。

问题:广搜与深搜找父结点哪个更好

李祝祺答:用广搜实现找树结点的父结点比用深搜好

问题:能否直接用二叉树前序遍历框架来编写森林的先根序遍历?

李芊答:可以用二叉树前序遍历框架编写先根遍历,因为二叉树与森林是可以等价转换的,访问一个结点的时候先得到它的值,访问左链的时候就是访问最左子结点,访问右链的时候变成访问它的右兄弟结点。先访问左链再访问右链,就是先根序遍历它的子树再遍历它的右兄弟,符合先根序遍历。

问题:能否直接用二叉树中序遍历框架来编写森林的后根序遍历?

李芊答:同理可以用中序遍历框架编写后根遍历,同样因为二叉树与森里实质上是等价的。先访问左链的时候访问它的最左子结点,这个点的子树(左链)都被访问过之后访问这个点的值,接着再访问它的右兄弟(右链)。与二叉树中序遍历一样。

问题:怎么证明n个结点的正权图用BF算法松弛n-1次即可得到最短路径?

谢毅泽答:如果松弛超过n次才得到最短路径,则必然存在一个结点被经过了两次,所以路径中有环。则去掉环之后路径长度应会更短。

第七章 图

问题:拓扑排序算法对于起始元素是否有要求?

杜若谷答:使用队列的方法需要起始点入度为0,使用深搜的方法对于入度没有要求。

问题:n个重量为1~n的球,给定一些球之间的重量比较关系,现在给每个球编号,在符合条件的前提下使得编号小的球重量小。(先保证1号球最轻,其次2号……)

郑子威答:,对于每一个重量比较关系,比如ab轻,那么就连一条从ba的边。根据所有重量比较关系就可以建出有n个结点的图。对这张图做拓扑排序,然后对得到的拓扑序列从1n编号即为答案。(答案可能不唯一)因为这样编号就保证了所有比当前球轻的球都已经被编号过了。

问题:如何判断最小生成数是否唯一

章嘉晨答:得到最小生成树后,扫描非树边,查看其两端点到LCA的路径上是否有与该边权值相等的边。若有表示不唯一,同时可以使用RMQ算法进行优化

问题:怎么知道图中所有顶点的入度?

高飙答:在建图的时候就可以统计每个顶点的入度并保存。

问题:拓扑排序是否可以用栈来取代队列?

吴鹏答:因为此时只是暂存一会要用的的点,并不要求先进先出或者后进先出,所

以用栈和队列都是可以的。只是用了栈和用队列的相比所产生的最终的排序输出一般会有所

不同(除非只有一个解)

问题:对于课件中的图,给出相应的广度优先遍历序列

邹良川答:课件中的图有3层,按广度优先规则可逐层遍历,为:a->b->d->e->f->c->g

问题:字母偏序问题(拓展题目)算法

邹良川答:做拓扑排序,若每次入度为零的点只有一个,则可唯一确定偏序关系;若有环,则矛盾;否则无法确定偏序关系

问题:在课程中讲解的最小生成树计数问题的算法中,是不是会漏掉两边边权相同但所连集合不同的情况?

郭秭含答:所连集合不同,则两边都会被选中,因而不会漏解

 问题:对于扩展的复杂图结构(含有自环和重边)存储结构应做怎样的改变?

许瑞琦答:在邻接矩阵中可以存储含有自环的图(对角线上元素非0即可),对于含有重边的图的邻接矩阵,则需在每个元素拉出一个链表来存储不同的边。而在图的邻接表中,则不许做任何改变,直接将自环和重边的终结点插入对应始节点对应的链表中即可。

问题:为何不允许一条边的起点与终点都是同一个顶点?

李芊答:不允许起点与终点都是同一个顶点,可能是因为从自己到自己的路径长度为0,是没有意义的,所以一般情况下不考虑。

问题:是否存在多条起点与终点都相同的边?

李芊答:图中不存在多条起点与终点都相同的边,因为我认为这样做也是无意义的,在数据结构里面边一个顶点到另一个顶点的边的性质是一定的,所以再多的边只是冗余,一般情况下也不用考虑。

问题:将“D[i][j].pre= D[v][j].pre 改为“ D[i][j].pre = v”是否可以?对于恢复最短路径,策略有何不同?那种更优?

李芊答:可以改成D[i][j].pre = v。用D[i][j].pre=D[v][j].pre可以保证了j之前最近的点是正确的,所以在恢复路径的时候可以从D[i][j].pre找到离j最近的点m,再用D[i][m].pre找到前面的点n…依此类推直到pre值为i时,就能找到从ij途径的所有点了。而采用D[i][j].pre=v可能遗失了(v, j)之间的点,所以需要找一次(i, v)之间的点和(v, j)之间的点。这样每次都要向两边找一次,找到之后还要想办法把两边路径合并,效率就会低很多。所以还是用D[i][j].pre=D[v][j].pre更优。