import networkx as nx

def drone_path(parcours_drone, G):
    """
    Utilise le parcours du drone comme base pour le parcours de la déneigeuse
    Params:
        parcours_drone: la liste des arêtes visitées par le drone
        G: le graphe du quartier original
    Return:
        Le parcours de la déneigeuse
    """
    parcours_deneigeuse = []
    for (u,v) in parcours_drone:
        if G.has_edge(u,v):
            parcours_deneigeuse.append((u,v))
        else:
            pcc = nx.shortest_path(G, u, v, weight='length')
            for i in range(len(pcc) - 1):
                parcours_deneigeuse.append((pcc[i], pcc[i+1]))
            parcours_deneigeuse.append((v,u))
            for i in range(len(pcc) - 1):
                parcours_deneigeuse.append((pcc[i], pcc[i+1]))
    return parcours_deneigeuse