Korteste rute i et nettverk

Du skal på togtur mellom 2 av de 13 følgende storbyene i Vest-Europa. Siden du er turist og skal se alle storbyene kan du kun gjøre en togreise hver dag uavhengig av distansen mellom byene. Du bestemmer deg for å lage et lite script som finner den korteste ruten mellom 2 noder i et nettverk med like lange kanter. Byene 1-13 er knyttet sammen i et nettverk med følgende kanter mellom følgende byer.

kanter = [

    ["1", "2"], ["2", "3"],

    ["3", "4"], ["2", "4"],

    ["4", "5"], ["5", "6"],

    ["2", "7"], ["2", "10"],

    ["7", "8"], ["8", "9"],

    ["9", "10"], ["10", "11"],

    ["11", "12"], ["11", "13"],

    ["12", "13"]

]

byer = {"1":"Rennes",

     "2":"Paris",

     "3":"Bordeuax",

     "4":"Lyon",

     "5":"Marseille",

     "6":"Montpellier",

     "7":"Brussel",

     "8":"Amsterdam",

     "9":"Køln",

     "10":"Frankfurt",

     "11":"Munchen",

     "12":"Hamburg",

     "13":"Berlin"}

Oppgaven er å skrive ut den korteste ruten mellom alle par av byer under med en rute per linje. Den første ruten skal være mellom by 1 (Rennes) og 2 (Paris), så 1-3, 1-4 .... 2-1. 2-3, 2-4 ... 13-11, 13-12. Når du skriver ut ruten skal den være på formatet -"startby"-"..."-"sluttby" slik at de første 13 rutene blir skrevet ut som følger.

-Rennes-Paris

-Rennes-Paris-Bordeuax

-Rennes-Paris-Lyon

-Rennes-Paris-Lyon-Marseille

-Rennes-Paris-Lyon-Marseille-Montpellier

-Rennes-Paris-Brussel

-Rennes-Paris-Brussel-Amsterdam

-Rennes-Paris-Frankfurt-Køln

-Rennes-Paris-Frankfurt

-Rennes-Paris-Frankfurt-Munchen

-Rennes-Paris-Frankfurt-Munchen-Hamburg

-Rennes-Paris-Frankfurt-Munchen-Berlin

-Paris-Rennes

[[ errors ]]

    
Output:
[[ output ]]