shortest_path.py

from copy import copy
from math import inf

def get_distance (a,b,connections):
    for con in connections:
        if (con[0]==a) and (con[1]==b):
            return con[2]
    return None

def get_path_distance (path,connections):
    if None==path:
        return None
    ret=0
    i=0
    while (i<(len(path)-1)):
        a=path[i]
        b=path[i+1]
        d=get_distance(a,b,connections)
        if d==None:
            return None
        ret+=d
        i+=1
    return ret

def select_origin (origin, connections):
    ret=[]
    for con in connections:
        if con[0]==origin:
            ret.append(con)
    return ret

def get_path (destiny, connections, step, path):
    if step==0:
        return path
    if path[-1]==destiny:
        return path
    origin=path[-1]
    ap=select_origin(origin,connections)
    ret=None
    note=inf
    for p in ap:
          if p[1] in path:
              continue
          path2=copy(path)
          path2.append(p[1])
          path2=get_path(destiny,connections,step-1,path2)
          if path2==None:
              continue
          n=get_path_distance(path2,connections)
          if n<note:
              note=n
              ret=path2
    return ret

def main():
    origin=input("Enter the name of the origin:")
    destiny=input("Enter the name of the destiny:")
    ncon=int(input("Enter the number of connections:"))
    connections=[]
    for _ in range(ncon):
        s=input("Enter origin,destiny,distance:")
        l=s.split(",")
        l[2]=float(l[2])
        connections.append(l)
    path=[origin]
    path=get_path(destiny,connections,ncon,path)
    if path:
        print(path)
    else:
        print("It is impossible.")

main()