很久没得写这些了，以前写的也找不到了，于是我打算利用晚上的时间从头写。一方面是让自己能更透彻的思考问题，顺便练手，另外一方面也是和大家有个交流机会。最近一段时间我先会写一些经典算法的理解或者题目解题，比如ACM、一些公司面试题目、平时在工作中容易使用到的，也有机会来进行一些问题的讨论。
如果是题解，我会注明题目的出处，有兴趣可以尝试解题并提交代码。题目解题我会优先选用Python编写，部分不支持Python的Online Judge我选用C++。限于自己的水平，有错误的地方还请指正言归正传，先从一个简单的题目入手：
特征距离
<题目来源：百度2017秋招， >
问题描述：
在一个无向图G=(V,E)中，定义顶点s到顶点t的特征距离是构成从顶点s->t的最短路径(shortest path)的边集中E'= {e1,e2...en}中最长的边的大小。目标是要找到这个所有最短路径中最大的特征距离。
问题比较明确了，最直接的解决问题思路是直接求出s->t的所有最短路径，再遍历所有的最短路径找出最长的边即可。
首先考虑选择单源点最短路径算法：
(1)Dijkstra(2)SPFA该图是一个不含有负权变的无向图，上面两种算法都可以采用，这里选择SPFA，这个算法的算法核心就是对队列中的顶点进行松弛操作：
dist[u] = min{dist[u], dist[v] + edge(u, v).wight}其实质是如果到达u的最短路径可以由到达顶点v的最短路径加上连接u,v边的权得到，并且比原来的路径更短，那么我们就可以用这条新的路径长度来更新到达u的最短路径，这样的操作称之为松弛操作。然后我们在整个图中不断尝试寻找这样的顶点进行松弛操作，直到不能再发现可以松弛的顶点。那么考虑能不能在SPFA松弛得到dist[v]的过程中记录到达顶点v的最长的边max_edge[v]呢？那么这样在一次SFPA后，在求得最短路径的同时也得到了题目所求的最长的边。
分析上面的松弛操作后，发现并不容易实现，原因是，对顶点u的任何一次松弛操作都不能确定edge(u,v)是否最终在到达u的最短路径中。由于每次需要获取最大的边，需要不断保留最大的那条边。一旦某个边不再是构成最短路径上的边的时候，那么这个结果就错误了。在松弛过程中去存储全部路径不是一个明智的选择。
我们在SPFA结束后，根据dist[]可以求出所有的最短路径
如果dist[u] == dist[v] + edge(u, v)，那么v必然是从源点到u的最短路径上的一个点。问题就似乎变得比较简单，我们可以从源点开始，来一个DFS，只需要是满足上面这个表达式的边，我们就对其进行扩展，再深搜这个边连接的顶点。当顶点搜索到我们的终点时，就获得一条从s->t的最路径，当DFS结束后可以获得所有路径。那么只需要找出其他最大的就是答案，如果不可达，直接输出No answer问题至此已经得到解决，使用python提交，1513ms，感觉速度慢了一些
分析了下，可能是最后在DFS所有的最短路径的时候消耗了比较多的时间由于我们并不关心具体的最短路径，也不关心这样的最短路径有多少条，而是只关心其中的最长的那条边，而这条边必然是所有边中的一条，遂想到枚举所有的边，然后测试该边是否在最短路径中，仍然需要使用dist[u] == dist[v] + edge(u, v)这个条件，但是，如果确定edge(u, v)就在到t的最短路径中呢？
考虑连结这条边的两个顶点u,v，如果dist[s->u] + edge(u, v).wight + dist[v->t]=dist[s->t]的话，显然edge(u,v)这边边在s->t的最短路径中
其中dist[s->u]就是dist[u]，edge(u, v)已知，dist[s->t]就是dist[t]，由于我们所求出的dist都是以s作为源点的，而dist[v->t]需要以v为源点，并且每次枚举不同的顶点v'都需要计算不同的dist[v'->t]，显然行不通，但是我们也发现一个特点是，我们每次都是计算终点为t的最短路径，如果我们把终点t作为源点，把所有边反向做一次SPFA,就只需要计算一次，就可以得到所有的dist[v'->t]，本题是个无向图，处理起来更方便后面提交，发现效率并没有显著提升，又改为SPFA+heap的方式，仍然没有提高，怀疑是我采用的python的输入方式所导致，中午休息的时候顺手拍了一个CPP的版的，并没有使用heap，然后只需要12ms，可见差距还是比较大。
下面是最后采用SPFA+heap优化的代码，DFS和枚举边的方式都有写：
import heapqconst_idx_vertex = 0const_idx_wight = 1def dfs(u, t, vertexes, dist, path, edge_l, res): if u == t: #print path r = 0 for l in edge_l: r = max(r, l) res.append(r) return for vertex in vertexes[u]: v = vertex[const_idx_vertex] w = vertex[const_idx_wight] if dist[u] + w == dist[v]: path.append(v) edge_l.append(w) dfs(v, t, vertexes, dist, path, edge_l, res) path.pop() edge_l.pop()def spfa(dist, src, n, vertexes): que = [] in_que = [False for i in range(n + 1)] que.append(src) in_que[src] = True dist[src] = 0 heap = [] heapq.heappush(heap, (0, src)) while len(heap) > 0: info = heapq.heappop(heap) u = info[1] in_que[u] = False for vertex in vertexes[u]: v = vertex[const_idx_vertex] w = vertex[const_idx_wight] if dist[v] > dist[u] + w or dist[v] < 0: dist[v] = dist[u] + w if not in_que[v]: heapq.heappush(heap, (dist[v], v)) in_que[v] = Truedef get_max_edge(dist, dist_rev, vertexes, t, n): ans = -1 for u in range(1, n + 1): for vertex in vertexes[u]: v = vertex[const_idx_vertex] w = vertex[const_idx_wight] if dist[u] != -1 and dist_rev[v] != -1 and dist[u] + w + dist_rev[v] == dist[t]: ans = max(ans, w) return ans if ans > 0 else "No answer"def main(): t_cases = int(raw_input()) for t_case in range(t_cases): temp = raw_input().split(' ') n = int(temp[0]) m = int(temp[1]) s = int(temp[2]) t = int(temp[3]) vertexes = [[] for i in range(n + 1)] for i in range(m): temp = raw_input().split(' ') u = int(temp[0]) v = int(temp[1]) w = int(temp[2]) vertexes[u].append([v, w]) vertexes[v].append([u, w]) dist = [-1 for i in range(n + 1)] ''' # Before improved the code res = [] path = [s] edge_l = [] ans = -1 spfa(dist, s, n, vertexes) if dist[t] > 0: dfs(s, t, vertexes, dist, path, edge_l, res) for re in res: ans = max(re, ans) if ans < 0: ans = 'No answer' print 'Case #{}: {}'.format(t_case + 1, ans) ''' dist_rev = [-1 for i in range(n + 1)] spfa(dist, s, n, vertexes) spfa(dist_rev, t, n, vertexes) print 'Case #{}: {}'.format(t_case + 1, get_max_edge(dist, dist_rev, vertexes, t, n))if __name__ == '__main__': main()