Dijkstra

from collections import defaultdict
from heapq import *
inf = 99999 # 不连通值
mtx_graph = [[0, 1, inf, 3, inf, inf, inf, inf, inf],
             [1, 0, 5, inf, 2, inf, inf, inf, inf],
             [inf, inf, 0, 1, inf, 6, inf, inf, inf],
             [inf, inf, inf, 0, inf, 7, inf, 9, inf],
             [inf, 2, 3, inf, 0, 4, 2, inf, 8],
             [inf, inf, 6, 7, inf, 0, inf, 2, inf],
             [inf, inf, inf, inf, inf, 1, 0, inf, 3],
             [inf, inf, inf, inf, inf, inf, 1, 0, 2],
             [inf, inf, inf, inf, 8, inf, 3, 2, 0]]
m_n = len(mtx_graph)#带权连接矩阵的阶数
edges = [] #保存连通的两个点之间的距离(点A、点B、距离)
for i in range(m_n):
    for j in range(m_n):
        if i!=j and mtx_graph[i][j]!=inf:
            edges.append([i,j,mtx_graph[i][j]])
            
def Dijkstra(edges, from_node, to_node):
    go_path = []
    to_node = to_node-1
    g = defaultdict(list)
    for l,r,c in edges:
        g[l].append((c,r))
    q, seen = [(0, from_node-1, ())], set()
    while q:
        (cost, v1, path) = heappop(q)#堆弹出当前路径最小成本
        if v1 not in seen:
            seen.add(v1)
            path = (v1, path)
            if v1 == to_node:
                break
            for c, v2 in g.get(v1, ()):
                if v2 not in seen:
                    heappush(q, (cost+c, v2, path))
                        
    if v1 != to_node: #无法到达
        return ['inf'], []
        
    if len(path)>0:
        left=path[0]
        go_path.append(left)
        right=path[1]
        while len(right)>0:
            left=right[0]
            go_path.append(left)
            right=right[1]
        go_path.reverse() #逆序变换
        for i in range(len(go_path)): #标号加1
            go_path[i] = go_path[i]+1
    return cost, go_path

leght, path = Dijkstra(edges, 1, 9)
print('最短距离为：'+str(leght))
print('前进路径为：'+str(path))  

Floyd

import numpy as np
inf = 99999 # 不连通值
mtx_graph = [[0, 1, inf, 3, inf, inf, inf, inf, inf],
             [1, 0, 5, inf, 2, inf, inf, inf, inf],
             [inf, inf, 0, 1, inf, 6, inf, inf, inf],
             [inf, inf, inf, 0, inf, 7, inf, 9, inf],
             [inf, 2, 3, inf, 0, 4, 2, inf, 8],
             [inf, inf, 6, 7, inf, 0, inf, 2, inf],
             [inf, inf, inf, inf, inf, 1, 0, inf, 3],
             [inf, inf, inf, inf, inf, inf, 1, 0, 2],
             [inf, inf, inf, inf, 8, inf, 3, 2, 0]]

def Floyd(graph):
    N = len(graph)
    A = np.array(graph)
    path = np.zeros((N,N))
    
    for i in range(0,N):
        for j in range(0,N):
            if A[i][j] != inf:
                path[i][j] = j
                
    for k in range(0,N):
        for i in range(0,N):
            for j in range(0,N):
                if A[i][k] + A[k][j] < A[i][j]:
                    A[i][j] = A[i][k] + A[k][j]
                    path[i][j] = path[i][k]
                    
    for i in range(0,N):
        for j in range(0,N):
            path[i][j] = path[i][j] + 1
            
    print('距离 = ')
    print(A)
    print('路径 = ')
    print(path)
    
Floyd(mtx_graph)

机场航线设计

import numpy as np
import pandas as pd
import matplotlib.pyplot as plt
data = pd.read_csv('flights.csv')
#将sched_dep_time转换为'std'—预定的出发时间
data['std'] = data.sched_dep_time.astype(str).str.replace('(\d{2}$)','') + \
            ':' + data.sched_dep_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
#将sched_arr_time转换为“sta”—预定到达时间
data['sta'] = data.sched_arr_time.astype(str).str.replace('(\d{2}$)','') + \
            ':' + data.sched_arr_time.astype(str).str.extract('(\d{2}$)', expand=False) + ':00'
#将dep_time转换为'atd' -实际出发时间
data['atd'] = data.dep_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)','') + ':' + \
            data.dep_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)',expand=False) + ':00'
#将arr_time转换为'ata' -实际到达时间
data['ata'] = data.arr_time.fillna(0).astype(np.int64).astype(str).str.replace('(\d{2}$)','') + ':' + \
            data.arr_time.fillna(0).astype(np.int64).astype(str).str.extract('(\d{2}$)',expand=False) + ':00'
#时间信息合并
data['date'] = pd.to_datetime(data[['year','month','day']])
data = data.drop(columns = ['year','month','day'])

#创建图
import networkx as nx
plt.figure(figsize = (15, 15)) #调整画布大小
FG = nx.from_pandas_edgelist(data, source='origin', target='dest', edge_attr=True,)
FG.nodes() # 查看所有节点
FG.edges()# 查看所有边
nx.draw_networkx(FG, with_labels=True) #快速查看图表,发现3个十分繁忙的机场
print(nx.algorithms.degree_centrality(FG))
print("Average density: ", nx.density(FG)) # 图的平均边密度
print("Average shortest path length: ", nx.average_shortest_path_length(FG))
#图中所有路径的平均最短路径长度
print("Average degree connectivity: ", nx.average_degree_connectivity(FG))
dijpath = nx.dijkstra_path(FG, source='JAX', target='DFW')
print("Shortest: ", dijpath)
shortpath = nx.dijkstra_path(FG, source='JAX', target='DFW', weight='air_time')
print("Fastest: ", shortpath)