第三章 图

关于图的存储方式分为邻接矩阵和邻接表两种;
关于图的遍历方式分为深度优先遍历和广度优先遍历;
对于无向图, 其所有生成树里面必有一颗边所加权值最小的树, 称为最小生成树. 最小生成树的实现算法有克鲁斯卡尔和普利姆算法, 其英文分别为 Kruskal, Prim.
迪杰斯特拉和弗洛伊德算法, 其英文分别为 Dijkstra, Floyd.

图的存储

邻接矩阵 & 邻接表

对于无向图, 有直接连线为 1, 无连线为 0.
对于有向图, 自身为 0, 可到达为 1, 不可到达为 ∞

点击显/隐代码

import networkx as nx
import matplotlib.pyplot as plt


# 类: 图_矩阵
class Graph_Matrix:
    """
    邻接矩阵 (Adjacency Matrix)
    """
    def __init__(self, vertices=[], matrix=[]):
        """
        :param vertices: 带有顶点id和矩阵索引的字典,如 {vertex:index}.
        :param matrix: 一个矩阵
        """
        self.matrix = matrix
        self.edges_dict = {}  # {(tail, head):weight}
        self.edges_array = []  # (tail, head, weight)
        self.vertices = vertices
        self.num_edges = 0
        # 如果提供邻接矩阵，则创建边列表
        if len(matrix) > 0:
            if len(vertices) != len(matrix):
                raise IndexError
            self.edges = self.getAllEdges()
            self.num_edges = len(self.edges)
        # 如果不提供邻接矩阵，但提供顶点列表，用0构建矩阵
        elif len(vertices) > 0:
            self.matrix = [[0 for col in range(len(vertices))] for row in range(len(vertices))]
        self.num_vertices = len(self.matrix)

    def isOutRange(self, x):  # 越界
        try:
            if x >= self.num_vertices or x <= 0:
                raise IndexError
        except IndexError:
            print("节点下标出界")

    def isEmpty(self):  # 是否为空
        if self.num_vertices == 0:
            self.num_vertices = len(self.matrix)
        return self.num_vertices == 0

    def add_vertex(self, key):  # 添加顶点
        if key not in self.vertices:
            self.vertices[key] = len(self.vertices) + 1
        # 添加一个顶点意味着添加一行和一列
        # 为每一行添加一列
        for i in range(self.getVerticesNumbers()):
            self.matrix[i].append(0)
        self.num_vertices += 1
        nRow = [0] * self.num_vertices
        self.matrix.append(nRow)

    def getVertex(self, key):  # 返回顶点
        pass

    def add_edges_from_list(self, edges_list):  # 边列表: [(tail, head, weight),()]
        for i in range(len(edges_list)):
            self.add_edge(edges_list[i][0], edges_list[i][1], edges_list[i][2], )

    def add_edge(self, tail, head, cost=0):  # 添加边
        if tail not in self.vertices:
            self.add_vertex(tail)
        if head not in self.vertices:
            self.add_vertex(head)
        # 对于目录矩阵
        self.matrix[self.vertices.index(tail)][self.vertices.index(head)] = cost
        # 对于非目录矩阵
        # self.matrix[self.vertices.index(fromV)][self.vertices.index(toV)] = \
        #   self.matrix[self.vertices.index(toV)][self.vertices.index(fromV)] = cost
        self.edges_dict[(tail, head)] = cost
        self.edges_array.append((tail, head, cost))
        self.num_edges = len(self.edges_dict)

    def getEdges(self, V):  # 返回边
        pass

    def getVerticesNumbers(self):  # 返回顶点数目
        if self.num_vertices == 0:
            self.num_vertices = len(self.matrix)
        return self.num_vertices

    def getAllVertices(self):  # 返回所有顶点
        return self.vertices

    def getAllEdges(self):  # 返回所有边
        for i in range(len(self.matrix)):
            for j in range(len(self.matrix)):
                if 0 < self.matrix[i][j] < float('inf'):
                    self.edges_dict[self.vertices[i], self.vertices[j]] = self.matrix[i][j]
                    self.edges_array.append([self.vertices[i], self.vertices[j], self.matrix[i][j]])
        return self.edges_array

    def __repr__(self):
        return str(''.join(str(i) for i in self.matrix))

    def to_do_vertex(self, i):
        print('vertex: %s' % (self.vertices[i]))

    def to_do_edge(self, w, k):
        print('edge tail: %s, edge head: %s, weight: %s' % (self.vertices[w], self.vertices[k], str(self.matrix[w][k])))


# 函数: 二维数组生成无向图
def create_undirected_matrix(my_graph, nodes, matrix):
    nodes,matrix = nodes,matrix
    return Graph_Matrix(nodes, matrix)


# 函数: 显示无向图
def draw_undircted_graph(my_graph):
    G = nx.Graph()  # 建立一个空的无向图G
    for node in my_graph.vertices:
        G.add_node(str(node))
    for edge in my_graph.edges:
        G.add_edge(str(edge[0]), str(edge[1]))
    print("节点:", G.nodes())  # 输出全部的节点： [1, 2, 3]
    print("边:", G.edges())  # 输出全部的边：[(2, 3)]
    print("边数:", G.number_of_edges())  # 输出边的数量：1
    nx.draw(G, with_labels=True)
    plt.savefig("undirected_graph.png")
    plt.show()


if __name__ == '__main__':
    my_graph = Graph_Matrix()    # 对象: my_graph
    nodes = [0, 1, 2, 3, 4, 5, 6, 7]
    matrix = [[0, 1, 1, 1, 0, 0, 0, 0],  # 0
              [1, 0, 0, 0, 1, 0, 1, 0],  # 1
              [1, 0, 0, 1, 0, 0, 0, 0],  # 2
              [1, 0, 1, 0, 1, 0, 0, 0],  # 3
              [0, 1, 0, 1, 0, 1, 1, 0],  # 4
              [0, 0, 0, 0, 1, 0, 0, 1],  # 5
              [0, 1, 0, 0, 1, 0, 0, 0],  # 6
              [0, 0, 0, 0, 0, 1, 0, 0]]  # 7
    created_graph = create_undirected_matrix(my_graph, nodes, matrix)    # 生成无向图
    draw_undircted_graph(created_graph)    # 显示无向图


# 二维数组生成有向图
def create_directed_matrix(my_graph, nodes, matrix):
    nodes,matrix = nodes,matrix
    # print(my_graph)
    return Graph_Matrix(nodes, matrix)


# 显示有向图，带权
def draw_directed_graph(my_graph):
    G = nx.DiGraph()  # 建立一个空的单边有向图G
    # G = nx.MultiDiGraph() #  # 建立一个空的多边有向图G
    for node in my_graph.vertices:
        G.add_node(str(node))
    G.add_weighted_edges_from(my_graph.edges_array)
    print("nodes:", G.nodes())  # 输出全部的节点
    print("edges:", G.edges())  # 输出全部的边
    print("number of edges:", G.number_of_edges())  # 输出边的数量
    # print('---------------------------')
    labels = nx.get_edge_attributes(G, "weight")
    print(type(labels))
    print(labels)
    for key, values in labels.items():
        # hang=[]
        # hang.append(list(key)[0])
        # hang.append(list(key)[1])
        weight = {}
        weight[list(key)[0] + "-" + list(key)[1]] = values
        # print(weight)
        labels[key] = weight
    # print(labels)
    # print('---------------------------')
    plt.figure(3, figsize=(12, 12))  # 设置画布大小，可以使节点间的距离变大，weight更加清晰
    pos = nx.circular_layout(G)
    nx.draw_networkx_nodes(G, pos=nx.circular_layout(G), nodelist=G.nodes, alpha=0.4, node_color='red', node_shape='v',
                           node_size=220)
    nx.draw_networkx_labels(G, pos=nx.circular_layout(G), font_color='k', alpha=1)
    nx.draw_networkx_edge_labels(G, pos=nx.circular_layout(G), edge_labels=labels, label_pos=0.3,
                                 font_size=7)  # 添加边的权重weight
    nx.draw(G, with_labels=True, pos=nx.circular_layout(G), node_size=1500, alpha=0.3, font_weight="bold", arrows=True,
            connectionstyle='arc3, rad = 0.1')  # 使用connectionstyle='arc3, rad = 0.1'绘制a->b与b->a两条边
    plt.savefig("directed_graph3.png")
    plt.show()


if __name__ == '__main__':
    my_graph = Graph_Matrix()
    nodes = ['0', '1', '2', '3']
    inf = float('inf')
    matrix = [[0, inf, inf, inf],  # a
              [3, 0, inf, 2],  # b
              [inf, 6, 0, inf],  # c
              [4, 2, inf, 0]]  # d
    created_graph = create_directed_matrix(my_graph, nodes, matrix)
    draw_directed_graph(created_graph)

邻接表

点击显/隐代码

class Vertex:
    def __init__(self,name):
        self.name=name
        self.next=[]
class Graph:
    def __init__(self):
        self.vertexList={}
    def addVertex(self,vertex):
        if vertex in self.vertexList:
            return
        self.vertexList[vertex]=Vertex(vertex)
    def addEdge(self,fromVertex,toVertex):
        if fromVertex==toVertex:
            return
        if fromVertex not in self.vertexList:
            print('vertexList has no: ',fromVertex)
            return
        if toVertex not in self.vertexList:
            print('vertexList has no: ',toVertex)
            return
        if toVertex not in self.vertexList[fromVertex].next:
            self.vertexList[fromVertex].next.append(toVertex)
        if fromVertex not in self.vertexList[toVertex].next:
            self.vertexList[toVertex].next.append(fromVertex)
    def removeVertex(self,vertex):
        if vertex in self.vertexList:
            removed=self.vertexList.pop(vertex)
            removed=removed.name
            for key,vertex in self.vertexList.items():
                if removed in vertex.next:
                    vertex.next.remove(removed)
    def removeEdge(self,fromVertex,toVertex):
        if fromVertex not in self.vertexList:
            if fromVertex not in self.vertexList:
                print('vertexList has no: ', fromVertex)
                return
            if toVertex not in self.vertexList:
                print('vertexList has no: ', toVertex)
                return
        if fromVertex in self.vertexList[toVertex].next:
            self.vertexList[fromVertex].next.remove(toVertex)
            self.vertexList[toVertex].next.remove(fromVertex)
G=Graph()
for i in range(1,8):
    G.addVertex(i)
for i in range(1,7):
    G.addEdge(i,i+1)
for i,g in G.vertexList.items():
    print(i,g.next)
print('remove node 2')
G.removeVertex(2)
for i,g in G.vertexList.items():
    print(i,g.next)
print("remove node 4 and node 3 `s edge")
G.removeEdge(4,3)
for i,g in G.vertexList.items():
    print(i,g.next)

邻接矩阵与邻接表的转换

点击显/隐代码

from math import inf
nodes = [0, 1, 2, 3, 4, 5, 6, 7]
matrix = [[0, 1, 1, 1, 0, 0, 0, 0],  # 0
          [1, 0, 0, 0, 1, 0, 1, 0],  # 1
          [1, 0, 0, 1, 0, 0, 0, 0],  # 2
          [1, 0, 1, 0, 1, 0, 0, 0],  # 3
          [0, 1, 0, 1, 0, 1, 1, 0],  # 4
          [0, 0, 0, 0, 1, 0, 0, 1],  # 5
          [0, 1, 0, 0, 1, 0, 0, 0],  # 6
          [0, 0, 0, 0, 0, 1, 0, 0]]  # 7
def matrix2list1(matrix):
    ll=ls=[]
    for i in range(len(matrix)):
        ls = []
        for j in range(len(matrix[0])):
            if matrix[i][j] == 0:    # 如果第i行第j列元素==0: 中断
                continue
            if matrix[i][j] == 1:    # 如果 第i行第j列元素==1: 追加第j个输值为一
                ls.append(j)
        ll.append(ls)    # 将每一行生成的列表嵌套在另一个列表里面
    return ll
print(matrix2list1(matrix))


def list12matrix(matrix):
    ls=[]; j=0;lb=[];lx=[]
    for i in range(len(matrix)):
            ls.extend(matrix[i])
    for i in range(max(ls)+1):
        lb=[]
        for j in range(max(ls)+1):    # 里面的每行小列表
            if j in matrix[i]:    # 如果循环的n次若为123
                lb.append(1)
            else:
                lb.append(0)
        lx.append(lb)
    return lx
matrix=[[1, 2, 3], [0, 4, 6], [0, 3], [0, 2, 4], [1, 3, 5, 6], [4, 7], [1, 4], [5]]
print('转换后的邻接表',list12matrix(matrix) )    # 打印: 转换后的邻接表

#
def matrix2list(matrix):
    ll = []
    for i in range(len(matrix)):
        ls = []
        for j in range(len(matrix[0])):
            if matrix[i][j] and matrix[i][j] != inf:
                ls.append((i, j, matrix[i][j]))
        ll.extend(ls)
    return ll

matrix = [
    [0, 2, inf, inf, inf],
    [2, 0, inf, 3, 2],
    [inf, inf, 0, inf, 1],
    [inf, 3, inf, 0, 4],
    [inf, 2, 1, 4, 0]
]
print('转换后的邻接表',matrix2list(matrix) )    # 打印: 转换后的邻接表
#

def list2matrix(table):
    N = 0
    for i in range(len(table)):
        N = max(table[i][0], N)
    ret = [[inf] * (N + 1) for _ in range(N + 1)]
    for i in range(N + 1):
        ret[i][i] = 0
    try:    # 有距离
        for i, j, w in table:
            ret[i][j] = w
    except:    # 无距离
        for i ,j in table:
            ret[i][j]=1
    return ret
tb1=[(0, 1), (1, 0), (1, 3), (1, 4), (2, 4), (3, 1), (3, 4), (4,1), (4, 2), (4, 3)]
# tb1=[(0, 1, 2), (1, 0, 2), (1, 3, 3), (1, 4, 2), (2, 4, 1), (3, 1, 3), (3, 4, 4), (4, 1, 2), (4, 2, 1), (4, 3, 4)]
print('转换后的邻接矩阵',list2matrix(tb1))    # 打印: 转换后的邻接矩阵

图的遍历

深度优先遍历 & 广度优先遍历

点击显/隐代码

from collections import deque  # 图的遍历广度优先遍历第二行


class Graph_traversal:
    def __init__(self, G):
        self.G = G

    def dftr(self, v, visited=set()):
        print(v, end='  ')
        visited.add(v)
        for i in G[v]:
            if i not in visited:
                self.dftr(i, visited)

    def dfti(self, v):
        visited, s = set(), [v]
        while s:
            i = s.pop()
            if i not in visited:
                print(i, end='  ')
                visited.add(i)
                s.extend(G[i])

    def bft(self, v):
        visited, q = {v}, deque([v])
        while q:
            u = q.popleft()
            print(u, end='  ')
            for i in G[u]:
                if i not in visited:
                    q.append(i)
                    visited.add(i)


if __name__ == "__main__":
    G = [{1, 2, 3},
         {0, 4, 6},
         {0, 3},
         {0, 2, 4},
         {1, 3, 5, 6},
         {4, 7},
         {1, 4},
         {5, }]
    gt = Graph_traversal(G)
    print('-' * 15, '图的遍历开始', '-' * 15)
    print('递归深度优先: ', end=''); gt.dftr(0); print()
    print('迭代深度优先: ', end=''); gt.dfti(0); print()
    print('广 度 优 先: ', end=''); gt.bft(0); print()
    print('-' * 15, '图的遍历结束', '-' * 15)

广度优先遍历

最小生成树

最小生成树是指对于有 n 个节点的无向连通图, 一颗边的权值总和最小的生成树.

点击显/隐算法思路

在本题中, 克鲁斯卡尔算法的思想如下:
寻找最小边长, 得’3’,连接 1 与 4; # [1, 4, 3]
再度寻找最小边长, 得’4’,连接 4 与 5; # [4, 5, 4]
再度寻找最小边长, 得’5’,连接 5 与 0; # [5, 0, 5]
再度寻找最小边长, 得’6’,连接 2 与 3; # [2, 3, 6]
再度寻找最小边长, 得’7’,但不可连接 1 与 0, 因为会成为闭环.
再度寻找最小边长, 得’8’,连接 3 与 4; # [3, 4, 8]
每个顶点均已连接到.z 最小生成树生成.

在本题中, 普利姆算法的思想如下:
从最小顶点开始, 得 0, 连接顶点0中所有边 (7, 5) 的最小边’5’所在的顶点, 即 5. # [0, 5, 5]
再度从这俩顶点开始, 连接顶点 0,5 中对于4,1,3,2的所有边
(7, 4, 10) 的最小边’4’所在的顶点, 即 4. # [5, 4, 4]
再度从这仨顶点开始, 连接顶点 0,5,4 中对于1,3,2的所有边
(7, 3, 8, 10) 的最小边’3’所在的顶点, 即 1. #[4, 1, 3]
再度从这伵顶点开始, 连接顶点 0,5,4,1 中对于3,2的所有边
(9, 8, 10) 的最小边’8’所在的顶点, 即 3. #[4, 3, 8]
再度从这伍顶点开始, 连接顶点 0,5,4,1,3 中对于2的所有边
(9, 6) 的最小边’6’所在的顶点, 即 2. # [3, 2, 6]
每个顶点均已连接到.z 最小生成树生成.

点击显/隐代码

from math import inf
class Minimum_spanning_tree():
    """类: 最小生成树"""
    def __init__(self, maps):
        self.maps = maps    # 邻接矩阵
        self.nodenum = self.get_nodenum()    # 顶点数
        self.edgenum = self.get_edgenum()    # 边数

    def get_nodenum(self):
        return len(self.maps)

    def get_edgenum(self):
        count = 0
        for i in range(self.nodenum):
            for j in range(i):
                if self.maps[i][j] > 0 and self.maps[i][j] < 9999:
                    count += 1
        return count

    def kruskal(self):
        res = []
        if self.nodenum <= 0 or self.edgenum < self.nodenum - 1:
            return res
        edge_list = []
        for i in range(self.nodenum):
            for j in range(i, self.nodenum):
                if self.maps[i][j] < 9999:
                    edge_list.append([i, j, self.maps[i][j]])
        edge_list.sort(key=lambda a: a[2])
        group = [[i] for i in range(self.nodenum)]
        for edge in edge_list:
            for i in range(len(group)):
                if edge[0] in group[i]:
                    m = i
                if edge[1] in group[i]:
                    n = i
            if m != n:
                res.append(edge)
                group[m],group[n] = group[m] + group[n],[]
        return res

    def prim(self):
        res = []
        if self.nodenum <= 0 or self.edgenum < self.nodenum - 1:
            return res
        res,seleted_node,candidate_node = [],[0],[i for i in range(1, self.nodenum)]
        while len(candidate_node) > 0:
            begin, end, minweight = 0, 0, inf
            for i in seleted_node:
                for j in candidate_node:
                    if self.maps[i][j] < minweight:
                        minweight,begin, end = self.maps[i][j],i, j
            res.append([begin, end, minweight])
            seleted_node.append(end)
            candidate_node.remove(end)
        return res


matrix = [[0, 7, inf, inf, inf, 5],
          [7, 0, 9, inf, 3, inf],
          [inf, 9, 0, 6, inf, inf],
          [inf, inf, 6, 0, 8, 10],
          [inf, 3, inf, 8, 0, 4],
          [5, inf, inf, 10, 4, 0]]
graph = Minimum_spanning_tree(matrix)
print('节点数据为:', graph.nodenum, '边数为:', graph.edgenum)
print('克鲁斯卡尔算法获得结果:', graph.kruskal(), '\n普　利　姆算法获得结果:',graph.prim())

最短路径

点击显/隐算法思路

在本题中, 迪杰斯特拉算法的思想如下:
首先选取一个顶点, 自拟0, 顶点0距离未到达的顶点 (1,2,3,4,5,6) 距离分别为 (2,3,∞,∞,∞,∞), 2距离最小, 故添加顶点 1;
已添加 [0,1], 顶点0距离未到达的顶点 (2,3,4,5,6) 距离分别为 (3,11,7,∞,∞), 故添加顶点 2;
已添加 [0,1,2], 顶点0距离未到达的顶点 (3,4,5,6) 中顶点4可以经过顶点1或3, 距离分别为 2+5或3+1, 故添加顶点4, 其为从顶点0出发, 经过顶点2到达顶点4.
已添加 [0,1,2,4], 顶点0距离未到达的顶点 (3,5,6) 中到达3的最小距离为3+1+6, 到达5的最小距离为3+7, 故随便选一个, 添加顶点 3, 经过顶点2与4到达顶点3.
已添加 [0,1,2,4,3], 顶点0距离未到达的顶点 (5,6) 中到达5的最小距离为3+7, 故添加顶点 5, 其经过顶点2到达顶点5.
已添加 [0,1,2,4,3,5], 顶点0距离未到达的顶点 (6) 中到达6的最小距离为3+1+15, 故添加顶点 6, 其经过顶点2,4到达顶点6.

点击显/隐代码

class Dijkstra:
    def __init__(self, n, edges, start, process=False,undirected=True):
        self.n,self.start,self.edges,self.undirected,self.process = n,start,edges,undirected,process
        self.dis,self.pre = [float('inf')] * n,[start] * n
        self.dijkstra()

    def dijkstra(self):
        mat = [[float('inf')] * self.n for _ in range(self.n)]
        for i in range(self.n):
            mat[i][i] = 0
        for i, j, w in self.edges:
            if i == self.start:
                self.dis[j] = w
            mat[i][j] = w
            if self.undirected:
                mat[j][i] = w
                if j == self.start:
                    self.dis[i] = w
        visited = [self.start]
        nodes = [i for i in range(self.n) if i != self.start]

        while nodes:
            k = nodes[0]
            for point in nodes:
                if self.dis[point] < self.dis[k]:
                    k = point
            visited.append(k)
            nodes.remove(k)
            if self.process == True:    # 康添加，显示元素加入过程，初始[0] [1, 2, 3, 4, 5, 6]
                print(visited, nodes)
            for point in nodes:
                if self.dis[point] > self.dis[k] + mat[k][point]:
                    self.dis[point],self.pre[point] = self.dis[k] + mat[k][point],k



    def __call__(self, j):
        if self.start == j:
            return 0, str(self.start)
        p = [j]
        while self.pre[p[-1]] != self.start:
            p.append(self.pre[p[-1]])
        p.append(self.start)
        return self.dis[j], '-→'.join(str(c) for c in reversed(p)) if self.dis[j] != float('inf') else ''


class Floyd:
    def __init__(self, n, edges, undirected=True):
        self.n = n
        self.mat = [[float('inf')] * n for _ in range(n)]
        for i in range(n):
            self.mat[i][i] = 0
        for i, j, w in edges:
            self.mat[i][j] = w
            if undirected:
                self.mat[j][i] = w
        self.pre = [[r] * n for r in range(n)]
        self.floyd()

    def floyd(self):
        for k in range(self.n):
            for i in range(self.n):
                for j in range(self.n):
                    if self.mat[i][j] > self.mat[i][k] + self.mat[k][j]:
                        self.mat[i][j] = self.mat[i][k] + self.mat[k][j]
                        self.pre[i][j] = k

    def __call__(self, i, j):
        if i == j:
            return 0, str(i)
        p = [i, j]
        k = 0
        while k < len(p) - 1:
            if self.pre[p[k]][p[k + 1]] == p[k]:
                k += 1
            else:
                p.insert(k + 1, self.pre[p[k]][p[k + 1]])
        return self.mat[i][j], '-→'.join(str(c) for c in p) if self.mat[i][j] != float('inf') else ''

es = [(0,2,3),
      (0,1,2),
      (1,2,4),
      (1,3,9),
      (1,4,5),
      (2,4,1),
      (2,5,7),
      (3,4,6),
      (5,4,8),
      (3,6,11),
      (6,4,15),
      (6,5,13)]
for i in range(7):
    for j in range(i + 1, 7):
        Djstr = Dijkstra(7, es, i)
        Flyd = Floyd(7, es)
        print('路径:', i,'->',j)
        print('dijkstra: 距离: {}, 路径: {}'.format(*Djstr(j)))    # dijkstra: 距离: 11, 路径: 3->6
        print('floyd: 距离: {}, 路径: {}'.format(*Flyd(i, j)))
        # # dijkstra: 距离: 11, 路径: 3->6
        # print('dijkstra: 距离: {}, 路径: {}'.format(*path(j)))  # dijkstra: 距离: 11, 路径: 3->6
        # print('dijkstra: 距离和路径分别为: {}'.format(path(j)))  # dijkstra: 距离和路径分别为: (11, '3->6')
        # a, b = path(j);
        # print('dijkstra: 距离: {}, 路径: {}'.format(a, b))  # dijkstra: 距离: 11, 路径: 3->6

for i in range(7):
    for j in range(0, 7):
        if j == 0:
            print()
        Djstr = Dijkstra(7, es, i)
        Flyd = Floyd(7, es)
        print('{}'.format(*Djstr(j)), end="\t")
        # print('{}'.format(*Flyd(i,j)), end="\t")

关键路径

在AOE网中，从源点到汇点的带权路径长度最大的路径为关键路径，关键路径上的活动为关键活动。
如何确定关键路径，首先要确定Ve[j], Vl[j], e[i], l[i]。

Ve[j] ：表示事件j 的最早发生时间，ETV（Earliest Time Of Vertex)，考查入边，弧尾ve+入边最大值
VI[j]： 表示事件j 的最迟发生时间，LTV（Latest Time Of Vertex)，考查出边，弧头vl−出边最小值。
e[i]：表示活动ai的最早开始时间，ETE(Earliest Time Of Edge)，弧尾的最早发生时间。
l[i]：表示活动ai的最迟开始时间，LTE(Lastest Time of Edge)，弧头的最迟发生时间减去边值。

如该图，该图的Ve与Vl如下：
|V|v1|v2|v3|v4|v5|v6|v7|v8|v9|
|ETV|0|6|4|5|7|7|16|14|18|
|LTV|0|6|6|8|7|10|16|14|18|

|V|v1|v2|v3|v4|v5|v6|v7|v8|v9|
|ETE|0|0|0|6|4|5|7|7|7|16|14|
|LTE|0|2|3|6|6|8|7|7|10|16|14|