文中涉及的关于最优路径以及相关算法的讨论，仅限静态下以距离作为优先考量的有向图、无向图或混合图的最优路径求解，不考虑时序相关性。时序相关或状态转移模型可参考图概率模型，诸如马尔可夫链、隐马尔科夫模型、条件随机场等。两者的主要区别在于后者求解的是随机过程中发生概率最大的时序转移路径。
图 (Graph) 是一种表示对象之间关系的数据结构，一个图由多个顶点，以及顶点之间的边构成。如果图中所有的边都是无向的 (即双向)，则这个图称为无向图；如果所有的边都是有向的 (可以理解为单向)，则这个图称为有向图；如果既有无向也有有向的边，则称为混合图。路径是交替的顶点和边构成的序列，表示从一个顶点转移至另一个顶点所经过的顶点和边。以下是有向图的示例：
为运行算法，我们统一构建一套有向图案例，一套无向图案例，以及一套混合图案例。考虑到代码简洁性的需求，不构建图和边的对象。案例中，每个顶点包含ID、邻接点、邻接边长三种信息。
import re class Vertex(object): def __init__(self,ID): self.id = ID #顶点ID self.neighbors = [] #邻点对象 self.edges = [] #与邻点相连的边长度 def gen_graphs(): sample = "(ID,Neighbors,Edge)(0,[1],[4])(1,[2,4,8],[12,10,8])(2,[3],[10])(3,[2,4,7],[10,12,6])(4,[7],[10])(5,[6],[12])(6,[11],[20])(7,[11],[10])(8,[1,4,10],[18,12,6])(9,[6,14],[10,10])(10,[5],[16])(11,[7,12],[10,4])(12,[9,14],[12,4])(13,[12,5],[6,22])(14,[10,15],[10,6])(15,[None],[None])" directed = [Vertex(i) for i in range(16)] #构建有向图 undirected = [Vertex(i) for i in range(16)] #构建无向图 mixed = [Vertex(i) for i in range(16)] #构建混合图 vertices_info = re.findall(r'([\w\[\],]+)',sample)[1:] for vertex_info in vertices_info: #遍历每一个顶点 ID = int(re.findall(r'[\w]+',vertex_info)[0]) #读取ID neighbors = eval(re.findall(r'\[[\w,]+\]',vertex_info)[0]) #读取邻点 directed[ID].neighbors = [directed[i] for i in neighbors if i is not None] undirected[ID].neighbors = [undirected[i] for i in neighbors if i is not None] mixed[ID].neighbors = [mixed[i] for i in neighbors if i is not None] edges = eval(re.findall(r'\[[\w,]+\]',vertex_info)[1]) #读取边 directed[ID].edges = [i for i in edges if i is not None] undirected[ID].edges = [i for i in edges if i is not None] mixed[ID].edges = [i for i in edges if i is not None] for vertex in directed: #构建有向非循环图 for i in range(len(vertex.neighbors)-1,-1,-1): neighbor = vertex.neighbors[i] if neighbor.id < vertex.id: del vertex.neighbors[i] del vertex.edges[i] for i in range(len(mixed)): #补充无向图对象缺失的边 vertex = mixed[i] for j in range(len(vertex.neighbors)): neighbor = vertex.neighbors[j] if vertex not in neighbor.neighbors: undirected[i].neighbors[j].neighbors.append(undirected[i]) undirected[i].neighbors[j].edges.append(undirected[i].edges[j]) return directed, undirected, mixed directed, undirected, mixed = gen_graphs()构建好案例后，使用代码对无向图案例进行简单的可视化，生成图像和代码如下：
import math import matplotlib.pyplot as plt #import seaborn as sns #sns.set(color_codes=True) plt.figure(figsize=(7,7)) Graph = undirected for i in range(len(Graph)): x, y = math.cos(i/16*2*math.pi),math.sin(i/16*2*math.pi) plt.scatter([x],[y],s=18,c='black',label=str(i)) plt.annotate(str(i), xy=(x, y), xycoords='data', xytext=(+5, +5), textcoords='offset points', fontsize=12) for j in range(len(Graph[i].neighbors)): if Graph[i].neighbors[j].id < Graph[i].id: continue x2, y2 = math.cos(Graph[i].neighbors[j].id/16*2*math.pi),math.sin(Graph[i].neighbors[j].id/16*2*math.pi) plt.plot([x,x2], [y,y2], linewidth=1,color='gray') plt.annotate('(%d)'%Graph[i].edges[j], xy=((x+x2)/2, (y+y2)/2), xycoords='data', xytext=(+0, +0), textcoords='offset points', color='gray', fontsize=10)拓扑排序仅能应用于有向非循环图，是对图中的所有顶点 V i V_i Vi ( i = 1 , . . . , n ) (i=1,...,n) (i=1,...,n) 进行统一排序，使得对于任意条边 ( V a (V_a (Va-> V b ) V_b) Vb)，满足 a < b a<b a<b。经过拓扑排序的图，能加速目标检索的效率，同时能够快速获取两个顶点间的上下游位置，应用场景包括学位课程之间的先修关系、面对对象程序类之间的继承，以及工程项目之间的调度等。需要注意的是，一个有向非循环图可能存在不止一种拓扑排序的结果。算法原理在于通过迭代，将无入度 (无上游顶点) 的顶点从原图中抽出放入队列中，直到所有顶点排序完毕。伪代码如下：
Algorithm Topological_Sort(Graph): Input: A directed and acyclic graph Graph. Output: Topological sorting array of vertex objects. initiate empty array sort while Graph is not empty do extract vertices with 0 in-degree from Graph to sort return sort
以下运用 random 模块将有向图案例打乱后进行拓扑排序。
import copy import random def Topological_Sort(Graph): sort = [] Graph = set(Graph) while len(Graph)>0: out_set = set() for V in Graph: out_set = out_set | set(V.neighbors) sort += list(Graph - out_set) Graph = out_set return sort disordered = copy.deepcopy(directed) random.shuffle(disordered) sort = Topological_Sort(disordered) for V in sort: print(str(V.id)+' ',end='')深度优先搜索 (Depth-First-Searching) 可以用于检测一个顶点是否可以通向另一个顶点，或检测一个图是否是连通图。其过程类似于牵着绳子走入迷宫，每一个拐角是一个顶点，当走到死角时，记录来过这里，沿着绳子的路线返回寻找下一个拐角。但在实际应用中全程只用一根绳子无疑是低效的，因此引入递归的思想，每到一个拐点切出多个绳头分头搜索。改进后的算法如下：
Algorithm DFS(U, Visited, path): Input: The point of search origin U, object Visited recording visited vertices, and path started from Vertex. Output: N/A. call process(U, path) # code block for processing vertex, i.e. export path or break recursion. for each downstream neighbor V near U do if V not in Visited then add V into Visited and path recursively call DFS(V, Visited, path)
以下使用准备好的混合图案例来运行该算法，检查该混合图是否是连通图。
class Visited_vertices: def __init__(self,U): self.vertices = [U] def DFS(Vertex,Visited,path): print(path) for V in Vertex.neighbors: if V not in Visited.vertices: Visited.vertices.append(V) path.append(V) DFS(V,Visited,path) U = mixed[0] DFS(U,Visited_vertices(U),[U]) len(Visited.vertices)!=len(mixed)广度优先搜索 (Breadth-First-Searching) 将顶点分为不同的层级，逐层向下检查，分层的依据是路径所包含边的数量。相对于深度优先搜索，广度优先搜索能够保证在边的数量上两个顶点间检索到的路径最短。算法如下：
Algorithm BFS(U): Input: The point of search origin U. Output: N/A. initialize queue level which includes the initial vertex U initialize queue next_level in concern of address of vertices in the next level initialize array visited recording visited vertices while level is non-empty do for each vertax V in level do call process(V) # code block for processing vertex, i.e. export path or break add unvisited neighbors of V into next_level and visited replace the vertices in level with the ones in next_level empty next
以下代码同样应用混合图，检测该图是否为连通图。出于代码的可读性考虑，以下代码没有记录路径，需要读者在理解算法后自行添加。
def BFS(U): level = {U} next_level = set() visited = {U} while len(level)>0: for V in level: print(V) next_level = next_level | (set(V.neighbors) - visited) visited = visited | set(V.neighbors) level = next_level next_level = set() return visited U = mixed[0] visited = BFS(U) len(visited)!=len(mixed)假如我们不希望每次检索两个顶点是否可达时，都从头开始进行深度优先或广度优先搜索，可以使用该算法进行信息增强，以加速后续检索，一劳永逸。该算法的原理在于每次迭代时，将所有满足可达性要求的 V k − 1 V_{k-1} Vk−1-> V k V_k Vk-> V k + 1 V_{k+1} Vk+1 的 V k − 1 V_{k-1} Vk−1 和 V k + 1 V_{k+1} Vk+1 单独建立联系，构建新的边 V k − 1 V_{k-1} Vk−1 -> V k + 1 V_{k+1} Vk+1。如此一来，多次迭代过后，所有可通达的配对 ( V a V_a Va, V b V_b Vb) 都将拥有直接关系，并获取两点间所有路径中的最短距离。最终生成的新的图称为原图的传递闭包。需要注意的是，该算法的时间复杂度为 O ( k n 3 ) O(kn^3) O(kn3)， k k k 为迭代次数，为保证所有可达顶点配对存在直接相连的边，算法的运算消耗最高可接近 O ( n 4 ) O(n^4) O(n4)。显而易见，当顶点的数量 n n n 逐渐增加时，算法的运行时间将灾难性地上涨。伪代码如下：
Algorithm Floyd_Warshall(Graph, max_iter): Input: A graph Graph either unweighted or weighted. Output: Transitive closure of Graph. for each epoch in {1,…,max_iter} do for each vertex V in Graph do for each pair (Va,Vb) in Graph with Va,Vb ≠ \ne ̸= V do if both edge (Va->V) and edge (V>Vb) are in Graph then add the bridge (Va->Vb) as new edge into Graph # if it’s not already present else replace existing edge weight if the bridge implies a shorter path return Graph
以下代码不规定最大迭代次数，通过在每一轮迭代结束时检测是否存在新添加的边，来决定是否停止迭代。同样使用混合图作为测试案例。
import copy def Floyd_Warshall(Graph): while True: add = False for V in Graph: pairs = [(Va,Vb) for Va in Graph if Va!=V for Vb in Graph if Vb!=V if Va!=Vb] for pair in pairs: Va,Vb = pair[0],pair[1] if (V in Va.neighbors) & (Vb in V.neighbors): if Vb not in Va.neighbors: add = True Va.neighbors.append(Vb) Va.edges.append(Va.edges[Va.neighbors.index(V)]+V.edges[V.neighbors.index(Vb)]) else: new_edge = Va.edges[Va.neighbors.index(V)] + V.edges[V.neighbors.index(Vb)] if new_edge < Va.edges[Va.neighbors.index(Vb)]: Va.edges[Va.neighbors.index(Vb)] = new_edge if add == False: break return Graph closure = Floyd_Warshall(copy.deepcopy(mixed))在现实应用中，边与边往往并不对等，公路之间长度不一致，网络线路之间传输速率不同。因而我们需要将更多信息纳入最优路径的考量中，而不仅仅只是 DFS 中边的数量。边与边具有不对等信息的图称为加权图，我们将所有的权重看成距离，探寻两个顶点之间总距离最小的路径，即为求解最短路径。最经典的应用场景包括求从一个路口到城市另一个路口的最短路线和距离。Dijkstra 算法的思想在于从源点出发，构建一个逐步扩张的“云”，每次迭代将云外离源点最近的顶点拉入到云内来，使云逐渐遍布全图。算法的时间复杂度为 O ( n 2 ) O(n^2) O(n2)，在最短路径问题上的表现远比 Floyd-Warshall 算法表现优异，是贪心算法应用在该类问题上的绝佳案例。伪代码：
Algorithm Dijkstra(U,Graph): Input: The point of search origin U and the weighted graph Graph . Output: Hash table recording shorted path distance from U to each vertex in Graph. initialize array cloud recording vertices which are drawn into the “cloud” initialize hash table dist as expected output while there is unvisited neighbor outside cloud do find nearest neighbor V* outside cloud pull V* from Graph to cloud update dist(V*) for each downstream neighbor V of V* that is already in cloud do if dist(V*) plus the weight between V* and V gets smaller than dist(V) then update dist(V) return dist
以下呈现 Python 实现。关于最优路径的获取只需在下述代码中加入一个与 dist 并行的哈希表即可，亦可通过从顶点出发捕获权重和重构最短路径树。
def Dijkstra(U,Graph): cloud = {U} bound = {U} #包含有未入云邻点的云内顶点，用于决策是否停止迭代 dist = {U:0} while len(bound)>0: origins = [V for V in bound for neighbor in V.neighbors if neighbor not in cloud] neighbors = [neighbor for V in bound for neighbor in V.neighbors if neighbor not in cloud] dists = [V.edges[i] + dist[V] for V in bound for i in range(len(V.neighbors)) if V.neighbors[i] not in cloud] if len(dists) == 0: break idx = dists.index(min(dists)) print('new path added to cloud: %s -> %s'%(origins[idx].id,neighbors[idx].id)) V_ = neighbors[idx] cloud.add(V_) bound.add(V_) dist[V_] = dists[idx] for V in list(bound): if len([neighbor for neighbor in V.neighbors if neighbor not in cloud]) == 0: bound.discard(V) neighbors = [neighbor for neighbor in V_.neighbors if neighbor in cloud] edges = [V_.edges[V_.neighbors.index(neighbor)] for neighbor in V_.neighbors if neighbor in cloud] for i in range(len(neighbors)): new_dist = dist[V_] + edges[i] if new_dist < dist[neighbors[i]]: dist[neighbors[i]] = new_dist return dist dist = Dijkstra(mixed[0],mixed)上文所讨论的算法都是基于两个顶点，求解两个顶点间的最短路径，而最小生成树 (MST, Minimum-Spanning-Tree) 旨在求解连通所有顶点的最短路径。Prim-Jarnik 算法正是基于这一类的问题，在 Dijkstra 算法的基础上做调整，以多个零入度顶点 (无上游顶点) 作为云的初始状态，而后不断找寻离云内顶点最近的邻点拉入到云内来，以此迭代，直至所有顶点访问完毕。如果不存在零入度点，则随机挑选一个加入到云中。
Algorithm Prim_Jarnik(Graph): Input: A weighted graphGraph. Output: Minimum overall weights along the optimal spanning path. initialize array cloud recording vertices which are drawn into the “cloud” initialize scalar dist with 0 extract 0 in-degree from Graph into cloud while Graph is not empty do find nearest neighbor V* outside cloud extract V* from Graph to cloud add in the edge length into dist return dist
我们使用混合图作为案例。
import copy def Prim_jarnik(Graph): Graph = copy.deepcopy(mixed) dist = 0 Graph = set(Graph) out_set = set() for V in Graph: out_set = out_set | set(V.neighbors) cloud = Graph - out_set if len(cloud) == 0: cloud.add(Graph[0]) Graph -= cloud bound = copy.copy(cloud) #包含有未入云邻点的云内顶点，用于简化邻点检索 while len(bound)>0: origins = [V for V in bound for neighbor in V.neighbors if neighbor not in cloud] neighbors = [neighbor for V in bound for neighbor in V.neighbors if neighbor not in cloud] dists = [V.edges[i] for V in bound for i in range(len(V.neighbors)) if V.neighbors[i] not in cloud] idx = dists.index(min(dists)) print('new path added to cloud: %s -> %s'%(origins[idx].id,neighbors[idx].id)) V_ = neighbors[idx] dist += dists[idx] cloud.add(V_) bound.add(V_) for V in list(bound): if len([neighbor for neighbor in V.neighbors if neighbor not in cloud]) == 0: bound.discard(V) return dist min_dist = Prim_jarnik(copy.deepcopy(mixed))另一种基于构建单元素集合集群，通过遍历所有边按权重合并集群的算法 Kruskal 算法，感兴趣的读者可以自行了解。
假设我们希望以最低的成本，从深圳出发乘飞机游遍中国的二线城市再回到深圳，遵循怎样的路径使得总费用最低。以上算法以树状结构从根节点出发遍历至全图搜寻路径，不考虑叶节点与根节点的联系，因而无法解决此类闭路问题。这一类问题统称为旅行商问题 (TSP, Travelling Salesman Problem)。蚁群算法 (ACO, Ant Colony Optimization) 模拟蚁群觅食行为，相关原理在于蚂蚁在觅食过程中会在经过道路上释放信息素，距离越长信息素浓度越低，后来的蚂蚁会根据该信息素判断是否遵循该路径，没有蚂蚁走的道路信息素会逐渐挥发，随着数量越来越多的蚂蚁出行，最优路径上的信息素浓度越来越高，最终凸显出来。蚁群算法同样可应用于非闭合路径的优化问题，其最具价值的设计在于反馈系统，每次迭代都使用正案例的路径进行一次反馈，从而逐渐拟合参数。
Algorithm ACO(Graph,M,max_iter): Input: A weighted and cyclic graph Graph, number of ants sent each epoch M, and maximum number of iterations max_iter. Output: The best closed-loop path and overall path distance. initiate pheromore parameter info for each edge at each vertex # assign equal weights for all linked edges at a vertex for each epoch t in {1,…,max_iter} do arbitrarily select vertex U as start position initiate M ants at U initiate object Yield recording sets of valid path with its last number of ants m algorithm recursion(U,M,path,Yield): for each unvisited vertex neighbor V of U do distribute m = M × \times × info(U,V) / / / ∑ i \sum_i ∑iinfo(U,V i _i i) ants to vertex V add V into path if searching ends then yield path and m into Yield else recursively call recursion(V,m,path,Yield) call algorithm recursion(U,M,path,Yield) and obtain set of pairs (path,m) if t equals to max_iter then return pair (path,m) with largest m else for each pair (path,m) do calculate dist as the overall length of edges on path for each vertex V on path do set V n e x t _{next} next as the vertex next to V on path update info(V,V n e x t _{next} next) by Δ \Delta Δinfo(V,V n e x t _{next} next) = m / / / dist # edges on shorter path obtain higher weights
通过将无向非循环图进行一定调整改为无向循环图后（将无向图顶点 0 和顶点 15 相连），该问题成为一类不完全 TSG 路径优化问题。不完全的意思在于，并非所有顶点皆可互通互联。这样，代码呈现更强的普适性，也更贴合现实 (毕竟两个城市之间可能存在无票情况)。
import copy def ACO(Graph,M,max_iter): for V in Graph: num = len(V.neighbors) V.info = [1e-6]*num for t in range(max_iter): U = Graph[0] class Yield_tmp: def __init__(self): self.pairs = [] def recursion(U,M,path,Yield): for i in range(len(U.neighbors)): V = U.neighbors[i] if (V not in path) or (V == Graph[0]): m = M * U.info[i] / sum(U.info) new_path = path + [V] if (len(new_path) == len(Graph)+1): Yield.pairs.append((new_path,m)) elif V != Graph[0]: recursion(V,m,new_path,Yield) Yield = Yield_tmp() recursion(U,M,[U],Yield) pairs = Yield.pairs def best(): ms = [pair[1] for pair in pairs] idx = ms.index(max(ms)) pair = pairs[idx] path = '->'.join(['%s'%V.id for V in pair[0]]) m = ms[idx] dist = sum([pair[0][i].edges[pair[0][i].neighbors.index(pair[0][i+1])] for i in range(len(pair[0])-1)]) print('Epoch %s, Distance %s, Ants %d(%.2f%%), Path %s'%(t+1,dist,m,m/M*100,path)) return path,dist,m if t == max_iter-1: return best() else: for pair in pairs: dist = sum([pair[0][i].edges[pair[0][i].neighbors.index(pair[0][i+1])] for i in range(len(pair[0])-1)]) m = pair[1] for i in range(len(pair[0])-1): V = pair[0][i] V_next = pair[0][i+1] idx = V.neighbors.index(V_next) V.info[idx] += m / dist best() def adjust(undirected): cyclic = copy.deepcopy(undirected) cyclic[0].neighbors.append(cyclic[-1]) cyclic[-1].neighbors.append(cyclic[0]) cyclic[0].edges.append(8) cyclic[-1].edges.append(8) return TSG M = 1e8 max_iter = 10 TSG = adjust(undirected) path,dist,m = ACO(TSG,M,max_iter)放置一亿只蚂蚁在 ID 为 0 的顶点开始搜寻，十次迭代后的运行结果如下：
Epoch 1, Distance 170, Ants 0(0.00%), Path 0->15->14->8->4->13->12->11->10->5->6->9->7->3->2->1->0 Epoch 2, Distance 170, Ants 1(0.00%), Path 0->15->14->8->4->13->12->11->10->5->6->9->7->3->2->1->0 Epoch 3, Distance 152, Ants 4(0.00%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 4, Distance 152, Ants 14(0.00%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 5, Distance 152, Ants 155(0.00%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 6, Distance 152, Ants 50146(0.05%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 7, Distance 152, Ants 60989822(60.99%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 8, Distance 152, Ants 99953481(99.95%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 9, Distance 152, Ants 99982359(99.98%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0 Epoch 10, Distance 152, Ants 99989117(99.99%), Path 0->1->2->3->7->9->6->5->4->13->12->11->10->8->14->15->0在应对动态的图数据时，可以加入额外的条件停止迭代，例如当三次迭代所获取的最优路径相同或两次迭代最优路径蚂蚁数量增长超过1%时提前停止。这样做的目的在于避免参数极端化，当图数据发生更新时 (例如在某两个顶点之间新添一条捷径)，能够最快适应新数据。
同时，受限于本文的案例规模，即使遍历全部可行路线也仅有 124 条，蚁群算法的真正效用未能体现。当我们希望从数百万条可行方案中挑出最优路径时 (例如城市路线规划)，蚁群算法才真正发挥作用。在这样的情况下，受限于硬件，计算机无法通过遍历或递归快速求出最优解，需要在遍历算法中加入终止条件。对于已经终止的路径，我们通过计算损失函数给予较优路径更高的反馈权重，从而达到迅速接近最优解的目的。
遗传算法启发于人类优质染色体在遗传过程中交叉与变异的行为，是一种基于概率的全局优化算法。由于其思想的特殊性，遗传算法对应用场景的限制较多。应用在求最优路径上，交叉意味着将不同的路径进行片段互换，因此仅能应用于所有顶点之间能直接互连互通的无向图，否则会出现交叉后新路径中上一个顶点无法通向下一个顶点的情况。
满足以上条件后，算法首先进行若干次随机遍历，生成不同方案 (即不同路径)，完成初始化。取出其中表现最好的若干条路径构成队列，根据各路径总长度赋予权重。该权重决定了在接下来的迭代中交叉的概率，表现越好则交叉概率越高。每一轮迭代，从现有的路径队列中进行随机交叉和变异得出新路径补充到原队列中，通过测算总长度淘汰表现末尾的路径。多轮迭代后，从剩下的路径中挑出既有最优路径。关于算法过程更详细的介绍可见：https://my.oschina.net/supremestone/blog/737733 。
遗传算法的优点在于可跳出局部最优解到达全局最优解，但同时需要保持较长时间毫无线索的迭代。
模拟退火算法借鉴固体退火原理以及蒙特卡洛模拟的随机求优过程，每一轮迭代对算法参数生成随机调整，例如在上述应用蚁群算法寻找最优路径时，增加非最优路径上的道路权重。对随机调整的效益进行评估，若对当前最优方案产生优化效果则直接接受并应用该调整；若该调整不能优化当前最优方案，则给予一定的接受比例，这一比例是与迭代次数相关的函数，随着迭代次数逐渐增加，接受比例随之下降。
该算法没有固定的应用场景和形式，更多的是一种思想，通常用于对其他算法的优化。常被拿出和贪心算法进行对比。贪心算法追求当前即刻的优化方案，多轮迭代过后容易陷在局部最优解；而模拟退火算法由于在初始时对错误调整的接受比例较大，无视负面效果，在进行多轮二重迭代过后更有可能得到全局最优值。其负面因素也是显而易见的：参数不易调整，同时运算时间过长，因而只有在参数较少的应用场景更具实用性。
