Težinski grafovi u SAGE-u

import sage.misc.banner
banner()

┌────────────────────────────────────────────────────────────────────┐
│ SageMath version 9.2, Release Date: 2020-10-24                     │
│ Using Python 3.8.6. Type "help()" for help.                        │
└────────────────────────────────────────────────────────────────────┘

from IPython.core.display import HTML

var('A B C D E F G H I S T')

(A, B, C, D, E, F, G, H, I, S, T)

Definiranje težinskog grafa

1. način

G1=Graph({A:{B:5,C:2,D:4,E:10},
          B:{D:8},
          C:{E:7,F:5},
          D:{E:6,G:2},
          E:{F:3,G:2,H:3},
          F:{H:2,I:4},
          G:{H:3},
          H:{I:5}
          },weighted=True)

pozicijeG1={A:[-1,0],B:[-1,1],C:[-1,-1],D:[0,1],E:[0,0],F:[0,-1],G:[1,1],H:[1,0],I:[1,-1]}

G1.plot(pos=pozicijeG1,edge_labels=True,figsize=[4,4])

G1.weighted_adjacency_matrix()

[ 0 10  2  0  0  4  5  0  0]
[10  0  7  0  2  6  0  3  3]
[ 2  7  0  0  0  0  0  0  5]
[ 0  0  0  0  0  0  0  5  4]
[ 0  2  0  0  0  2  0  3  0]
[ 4  6  0  0  2  0  8  0  0]
[ 5  0  0  0  0  8  0  0  0]
[ 0  3  0  5  3  0  0  0  2]
[ 0  3  5  4  0  0  0  2  0]

G1.vertices()

[A, E, C, I, G, D, B, H, F]

2. način

matrica=G1.weighted_adjacency_matrix()

G2=Graph(matrica,format="weighted_adjacency_matrix")

G2.vertices()

[0, 1, 2, 3, 4, 5, 6, 7, 8]

pozicijeG2={3:[-1,0],0:[-1,1],7:[-1,-1],5:[0,1],2:[0,0],8:[0,-1],6:[1,1],4:[1,0],1:[1,-1]}

G2.plot(pos=pozicijeG2,edge_labels=True,figsize=[4,4])

3. način

Možemo koristiti NetworkX modul.

import networkx as nx

G3=nx.read_edgelist("tezinskiGraf1_edgelist.sage",nodetype=str)

pozicije={'A':(0,2),'B':(0,4),'C':(0,0),'D':(2,4),'E':(2,2),'F':(2,0),'G':(4,4),'H':(4,2),'I':(4,0)}
nx.draw(G3,pos=pozicije,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(G3,pos=pozicije,edge_labels=nx.get_edge_attributes(G3,'weight'));

Najkraći putovi u težinskim grafovima

Najkraći putovi od vrha A prema svim preostalim vrhovima

Po defaultu je by_weight=False, što znači da će metoda shortest_paths zanemariti težine bridova i tražiti najkraće putove u pripadnom netežinskom grafu pomoću BFS algoritma. Ako stavimo by_weight=True, tada će se uzeti težine u obzir i koristit će se Dijkstrin algoritam. Potpuno ista situacija je i za ostale slične metode koje se dolje spominju.

G1.shortest_paths(A)

{A: [A],
 B: [A, B],
 D: [A, D],
 C: [A, C],
 E: [A, E],
 F: [A, E, F],
 H: [A, E, H],
 G: [A, E, G],
 I: [A, E, H, I]}

G1.shortest_paths(A,by_weight=True)

{A: [A],
 E: [A, D, G, E],
 C: [A, C],
 I: [A, C, F, I],
 G: [A, D, G],
 D: [A, D],
 B: [A, B],
 H: [A, D, G, H],
 F: [A, C, F]}

nx.shortest_path(G3,"A")

{'A': ['A'],
 'B': ['A', 'B'],
 'C': ['A', 'C'],
 'D': ['A', 'D'],
 'E': ['A', 'E'],
 'F': ['A', 'C', 'F'],
 'G': ['A', 'D', 'G'],
 'H': ['A', 'E', 'H'],
 'I': ['A', 'C', 'F', 'I']}

nx.single_source_dijkstra_path(G3,'A')

{'A': ['A'],
 'B': ['A', 'B'],
 'C': ['A', 'C'],
 'D': ['A', 'D'],
 'E': ['A', 'D', 'G', 'E'],
 'F': ['A', 'C', 'F'],
 'G': ['A', 'D', 'G'],
 'H': ['A', 'D', 'G', 'H'],
 'I': ['A', 'C', 'F', 'I']}

Udaljenosti od vrha A prema svim preostalim vrhovima

G1.shortest_path_lengths(A)

{A: 0, B: 1, D: 1, C: 1, E: 1, F: 2, H: 2, G: 2, I: 3}

G1.shortest_path_lengths(A,by_weight=True)

{A: 0, E: 8, C: 2, I: 11, G: 6, D: 4, B: 5, H: 9, F: 7}

nx.shortest_path_length(G3,"A")

{'A': 0, 'E': 1, 'B': 1, 'D': 1, 'C': 1, 'F': 2, 'G': 2, 'H': 2, 'I': 3}

nx.single_source_dijkstra_path_length(G3,'A')

{'A': 0, 'C': 2, 'D': 4, 'B': 5, 'G': 6, 'F': 7, 'E': 8, 'H': 9, 'I': 11}

Najkraći putovi od vrha C prema svim preostalim vrhovima

G1.shortest_paths(C)

{C: [C],
 F: [C, F],
 E: [C, E],
 A: [C, A],
 B: [C, A, B],
 D: [C, A, D],
 H: [C, E, H],
 G: [C, E, G],
 I: [C, F, I]}

G1.shortest_paths(C,by_weight=True)

{A: [C, A],
 E: [C, E],
 C: [C],
 I: [C, F, I],
 G: [C, A, D, G],
 D: [C, A, D],
 B: [C, A, B],
 H: [C, F, H],
 F: [C, F]}

nx.shortest_path(G3,"C")

{'C': ['C'],
 'A': ['C', 'A'],
 'E': ['C', 'E'],
 'F': ['C', 'F'],
 'B': ['C', 'A', 'B'],
 'D': ['C', 'A', 'D'],
 'G': ['C', 'E', 'G'],
 'H': ['C', 'E', 'H'],
 'I': ['C', 'F', 'I']}

nx.single_source_dijkstra_path(G3,"C")

{'C': ['C'],
 'A': ['C', 'A'],
 'E': ['C', 'E'],
 'F': ['C', 'F'],
 'B': ['C', 'A', 'B'],
 'D': ['C', 'A', 'D'],
 'H': ['C', 'F', 'H'],
 'I': ['C', 'F', 'I'],
 'G': ['C', 'A', 'D', 'G']}

Udaljenosti od vrha C prema svim preostalim vrhovima

G1.shortest_path_lengths(C)

{C: 0, F: 1, E: 1, A: 1, B: 2, D: 2, H: 2, G: 2, I: 2}

G1.shortest_path_lengths(C,by_weight=True)

{A: 2, E: 7, C: 0, I: 9, G: 8, D: 6, B: 7, H: 7, F: 5}

nx.shortest_path_length(G3,"C")

{'C': 0, 'F': 1, 'A': 1, 'E': 1, 'G': 2, 'I': 2, 'B': 2, 'D': 2, 'H': 2}

nx.single_source_dijkstra_path_length(G3,"C")

{'C': 0, 'A': 2, 'F': 5, 'D': 6, 'E': 7, 'B': 7, 'H': 7, 'G': 8, 'I': 9}

Najkraći put od vha A do vrha E

G1.shortest_path(A,E)

[A, E]

G1.shortest_path(A,E,by_weight=True)

[A, D, G, E]

nx.shortest_path(G3,"A","E")

['A', 'E']

nx.dijkstra_path(G3,"A","E")

['A', 'D', 'G', 'E']

Udaljenost između vrhova A i E

G1.shortest_path_length(A,E)

1

G1.shortest_path_length(A,E,by_weight=True)

8

nx.shortest_path_length(G3,"A","E")

1

nx.dijkstra_path_length(G3,"A","E")

8

Najkraći put od vrha F do vrha B

G1.shortest_path(F,B)

[F, E, A, B]

G1.shortest_path(F,B,by_weight=True)

[F, C, A, B]

nx.shortest_path(G3,"F","B")

['F', 'C', 'A', 'B']

nx.dijkstra_path(G3,"F","B")

['F', 'C', 'A', 'B']

Udaljenost između vrhova F i B

G1.shortest_path_length(F,B)

3

G1.shortest_path_length(F,B,by_weight=True)

12

nx.shortest_path_length(G3,"F","B")

3

nx.dijkstra_path_length(G3,"F","B")

12

možemo definirati svoju funkciju koja će nam ispisati konačne oznake vrhova onako kako mi provodimo Dijkstrin algoritam ručno

def rucni_dijkstra(graf,vrh):
    udaljenosti=graf.shortest_path_lengths(vrh,by_weight=True)
    putovi=graf.shortest_paths(vrh,by_weight=True)
    vrhovi=graf.vertices()
    oznake=[]
    for v in vrhovi:
        if v==vrh:
            oznake.append(("-",0))
        else:
            oznake.append((putovi[v][-2],udaljenosti[v]))
    return table([vrhovi,oznake])

Najkraći putovi od vrha A

rucni_dijkstra(G1,A)

$A$	$E$	$C$	$I$	$G$	$D$	$B$	$H$	$F$
$\left(-, 0\right)$	$\left(G, 8\right)$	$\left(A, 2\right)$	$\left(F, 11\right)$	$\left(D, 6\right)$	$\left(A, 4\right)$	$\left(A, 5\right)$	$\left(G, 9\right)$	$\left(C, 7\right)$

Najkraći putovi od vrha B

rucni_dijkstra(G1,B)

$A$	$E$	$C$	$I$	$G$	$D$	$B$	$H$	$F$
$\left(B, 5\right)$	$\left(G, 12\right)$	$\left(A, 7\right)$	$\left(F, 16\right)$	$\left(D, 10\right)$	$\left(B, 8\right)$	$\left(-, 0\right)$	$\left(G, 13\right)$	$\left(C, 12\right)$

Ako želimo najkraći put istaknuti na grafu, definiramo svoju funkciju koja će to raditi.

def najkraci_put(G,v1,v2,raspored_vrhova=None,laj="circular"):
    put=G.shortest_path(v1,v2,by_weight=True)
    bridovi=G.edges(labels=False)
    bridovi_put=[]
    for i in range(len(put)-1):
        if (put[i],put[i+1]) in bridovi:
            bridovi_put.append((put[i],put[i+1]))
        else:
            bridovi_put.append((put[i+1],put[i]))
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={"red":bridovi_put},vertex_colors={"cyan":[v1,v2]},layout=laj,edge_labels=True)
    else:
        slika=G.plot(edge_colors={"red":bridovi_put},vertex_colors={"cyan":[v1,v2]},pos=raspored_vrhova,edge_labels=True)
    return slika

najkraci_put(G1,A,E,raspored_vrhova=pozicijeG1).show(figsize=[4,4])

najkraci_put(G1,F,B,raspored_vrhova=pozicijeG1).show(figsize=[4,4])

najkraci_put(G1,A,H,raspored_vrhova=pozicijeG1).show(figsize=[4,4])

Ako želimo istaknuti stablo najkraćih putova iz nekog vrha na grafu, definiramo svoju funkciju koja će to raditi

def stablo_najkracih_putova(G,v0,raspored_vrhova=None,laj="circular"):
    stablo=G.shortest_paths(v0,by_weight=True)
    bridovi=G.edges(labels=False)
    bridovi_stablo=[]
    for k in stablo:
        if k!=v0:
            for i in range(len(stablo[k])-1):
                if ((stablo[k][i],stablo[k][i+1]) in bridovi) and (not((stablo[k][i],stablo[k][i+1]) in bridovi_stablo)):
                    bridovi_stablo.append((stablo[k][i],stablo[k][i+1]))
                elif ((stablo[k][i+1],stablo[k][i]) in bridovi) and (not((stablo[k][i+1],stablo[k][i]) in bridovi_stablo)):
                    bridovi_stablo.append((stablo[k][i+1],stablo[k][i]))
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={"red":bridovi_stablo},vertex_colors={"cyan":[v0]},layout=laj,edge_labels=True)
    else:
        slika=G.plot(edge_colors={"red":bridovi_stablo},vertex_colors={"cyan":[v0]},pos=raspored_vrhova,edge_labels=True)
    return slika

stablo_najkracih_putova(G1,A,raspored_vrhova=pozicijeG1).show(figsize=[4,4])

stablo_najkracih_putova(G1,B,raspored_vrhova=pozicijeG1).show(figsize=[4,4])

Floyd-Warshallov algoritam

Na izlazu daje uređeni par (udaljenosti, prethodnici). Prva komponenta udaljenosti je rječnik čiji ključevi su vrhovi težinskog grafa, a vrijednosti ključeva su ponovno rječnici tako da je udaljenosti[u][v] jednako duljini najkraćeg puta od vrha u do vrha v u težinskom grafu. Druga komponenta prethodnici je također rječnik čiji ključevi su vrhovi težinskog grafa, a vrijednosti ključeva su ponovo rječnici tako da je prethodnici[u][v] prethodnik vrha v na najkraćem putu od vrha u do vrha v u težinskom grafu.

G1.shortest_path_all_pairs()

({A: {A: 0, E: 1, C: 1, I: 3, G: 2, D: 1, B: 1, H: 2, F: 2},
  E: {A: 1, E: 0, C: 1, I: 2, G: 1, D: 1, B: 2, H: 1, F: 1},
  C: {A: 1, E: 1, C: 0, I: 2, G: 2, D: 2, B: 2, H: 2, F: 1},
  I: {A: 3, E: 2, C: 2, I: 0, G: 2, D: 3, B: 4, H: 1, F: 1},
  G: {A: 2, E: 1, C: 2, I: 2, G: 0, D: 1, B: 2, H: 1, F: 2},
  D: {A: 1, E: 1, C: 2, I: 3, G: 1, D: 0, B: 1, H: 2, F: 2},
  B: {A: 1, E: 2, C: 2, I: 4, G: 2, D: 1, B: 0, H: 3, F: 3},
  H: {A: 2, E: 1, C: 2, I: 1, G: 1, D: 2, B: 3, H: 0, F: 1},
  F: {A: 2, E: 1, C: 1, I: 1, G: 2, D: 2, B: 3, H: 1, F: 0}},
 {A: {A: None, E: A, C: A, I: H, G: E, D: A, B: A, H: E, F: E},
  E: {A: E, E: None, C: E, I: H, G: E, D: E, B: A, H: E, F: E},
  C: {A: C, E: C, C: None, I: F, G: E, D: A, B: A, H: E, F: C},
  I: {A: E, E: H, C: F, I: None, G: H, D: E, B: A, H: I, F: I},
  G: {A: E, E: G, C: E, I: H, G: None, D: G, B: D, H: G, F: E},
  D: {A: D, E: D, C: A, I: H, G: D, D: None, B: D, H: E, F: E},
  B: {A: B, E: A, C: A, I: H, G: D, D: B, B: None, H: E, F: E},
  H: {A: E, E: H, C: E, I: H, G: H, D: E, B: A, H: None, F: H},
  F: {A: E, E: F, C: F, I: F, G: E, D: E, B: A, H: F, F: None}})

samo udaljenosti između pojedinih vrhova

G1.shortest_path_all_pairs()[0]

{A: {A: 0, E: 1, C: 1, I: 3, G: 2, D: 1, B: 1, H: 2, F: 2},
 E: {A: 1, E: 0, C: 1, I: 2, G: 1, D: 1, B: 2, H: 1, F: 1},
 C: {A: 1, E: 1, C: 0, I: 2, G: 2, D: 2, B: 2, H: 2, F: 1},
 I: {A: 3, E: 2, C: 2, I: 0, G: 2, D: 3, B: 4, H: 1, F: 1},
 G: {A: 2, E: 1, C: 2, I: 2, G: 0, D: 1, B: 2, H: 1, F: 2},
 D: {A: 1, E: 1, C: 2, I: 3, G: 1, D: 0, B: 1, H: 2, F: 2},
 B: {A: 1, E: 2, C: 2, I: 4, G: 2, D: 1, B: 0, H: 3, F: 3},
 H: {A: 2, E: 1, C: 2, I: 1, G: 1, D: 2, B: 3, H: 0, F: 1},
 F: {A: 2, E: 1, C: 1, I: 1, G: 2, D: 2, B: 3, H: 1, F: 0}}

samo prethodnici vrhova na odgovarajućim najkraćim putovima

G1.shortest_path_all_pairs()[1]

{A: {A: None, E: A, C: A, I: H, G: E, D: A, B: A, H: E, F: E},
 E: {A: E, E: None, C: E, I: H, G: E, D: E, B: A, H: E, F: E},
 C: {A: C, E: C, C: None, I: F, G: E, D: A, B: A, H: E, F: C},
 I: {A: E, E: H, C: F, I: None, G: H, D: E, B: A, H: I, F: I},
 G: {A: E, E: G, C: E, I: H, G: None, D: G, B: D, H: G, F: E},
 D: {A: D, E: D, C: A, I: H, G: D, D: None, B: D, H: E, F: E},
 B: {A: B, E: A, C: A, I: H, G: D, D: B, B: None, H: E, F: E},
 H: {A: E, E: H, C: E, I: H, G: H, D: E, B: A, H: None, F: H},
 F: {A: E, E: F, C: F, I: F, G: E, D: E, B: A, H: F, F: None}}

Slično radi i floyd_warshall metoda u networkx modulu.

nx.floyd_warshall_predecessor_and_distance(G3)

({'A': {'B': 'A',
   'C': 'A',
   'D': 'A',
   'E': 'G',
   'F': 'C',
   'G': 'D',
   'H': 'F',
   'I': 'F'},
  'B': {'A': 'B',
   'D': 'B',
   'C': 'A',
   'E': 'G',
   'F': 'C',
   'G': 'D',
   'H': 'G',
   'I': 'F'},
  'C': {'A': 'C',
   'E': 'C',
   'F': 'C',
   'B': 'A',
   'D': 'A',
   'G': 'D',
   'H': 'F',
   'I': 'F'},
  'D': {'A': 'D',
   'B': 'D',
   'E': 'G',
   'G': 'D',
   'C': 'A',
   'F': 'E',
   'H': 'G',
   'I': 'H'},
  'E': {'A': 'D',
   'C': 'E',
   'D': 'G',
   'F': 'E',
   'G': 'E',
   'H': 'E',
   'B': 'D',
   'I': 'F'},
  'F': {'C': 'F',
   'E': 'F',
   'H': 'F',
   'I': 'F',
   'A': 'C',
   'B': 'A',
   'D': 'G',
   'G': 'E'},
  'G': {'D': 'G',
   'E': 'G',
   'H': 'G',
   'A': 'D',
   'B': 'D',
   'C': 'A',
   'F': 'E',
   'I': 'H'},
  'H': {'E': 'H',
   'F': 'H',
   'G': 'H',
   'I': 'H',
   'A': 'C',
   'B': 'D',
   'C': 'F',
   'D': 'G'},
  'I': {'F': 'I',
   'H': 'I',
   'A': 'C',
   'B': 'A',
   'C': 'F',
   'D': 'G',
   'E': 'F',
   'G': 'H'}},
 {'A': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83310>, {'A': 0, 'B': 5, 'C': 2, 'D': 4, 'E': 8, 'F': 7, 'G': 6, 'H': 9, 'I': 11}),
  'B': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff834c0>, {'B': 0, 'A': 5, 'D': 8, 'C': 7, 'E': 12, 'F': 12, 'G': 10, 'H': 13, 'I': 16}),
  'C': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83550>, {'C': 0, 'A': 2, 'E': 7, 'F': 5, 'B': 7, 'D': 6, 'G': 8, 'H': 7, 'I': 9}),
  'D': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff835e0>, {'D': 0, 'A': 4, 'B': 8, 'E': 4, 'G': 2, 'C': 6, 'F': 7, 'H': 5, 'I': 10}),
  'E': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83670>, {'E': 0, 'A': 8, 'C': 7, 'D': 4, 'F': 3, 'G': 2, 'H': 3, 'B': 12, 'I': 7}),
  'F': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83700>, {'F': 0, 'C': 5, 'E': 3, 'H': 2, 'I': 4, 'A': 7, 'B': 12, 'D': 7, 'G': 5}),
  'G': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83790>, {'G': 0, 'D': 2, 'E': 2, 'H': 3, 'A': 6, 'B': 10, 'C': 8, 'F': 5, 'I': 8}),
  'H': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff83820>, {'H': 0, 'E': 3, 'F': 2, 'G': 3, 'I': 5, 'A': 9, 'B': 13, 'C': 7, 'D': 5}),
  'I': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff838b0>, {'I': 0, 'F': 4, 'H': 5, 'A': 11, 'B': 16, 'C': 9, 'D': 10, 'E': 7, 'G': 8})})

nx.floyd_warshall_predecessor_and_distance(G3)[0]

{'A': {'B': 'A',
  'C': 'A',
  'D': 'A',
  'E': 'G',
  'F': 'C',
  'G': 'D',
  'H': 'F',
  'I': 'F'},
 'B': {'A': 'B',
  'D': 'B',
  'C': 'A',
  'E': 'G',
  'F': 'C',
  'G': 'D',
  'H': 'G',
  'I': 'F'},
 'C': {'A': 'C',
  'E': 'C',
  'F': 'C',
  'B': 'A',
  'D': 'A',
  'G': 'D',
  'H': 'F',
  'I': 'F'},
 'D': {'A': 'D',
  'B': 'D',
  'E': 'G',
  'G': 'D',
  'C': 'A',
  'F': 'E',
  'H': 'G',
  'I': 'H'},
 'E': {'A': 'D',
  'C': 'E',
  'D': 'G',
  'F': 'E',
  'G': 'E',
  'H': 'E',
  'B': 'D',
  'I': 'F'},
 'F': {'C': 'F',
  'E': 'F',
  'H': 'F',
  'I': 'F',
  'A': 'C',
  'B': 'A',
  'D': 'G',
  'G': 'E'},
 'G': {'D': 'G',
  'E': 'G',
  'H': 'G',
  'A': 'D',
  'B': 'D',
  'C': 'A',
  'F': 'E',
  'I': 'H'},
 'H': {'E': 'H',
  'F': 'H',
  'G': 'H',
  'I': 'H',
  'A': 'C',
  'B': 'D',
  'C': 'F',
  'D': 'G'},
 'I': {'F': 'I',
  'H': 'I',
  'A': 'C',
  'B': 'A',
  'C': 'F',
  'D': 'G',
  'E': 'F',
  'G': 'H'}}

nx.floyd_warshall_predecessor_and_distance(G3)[1]

{'A': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b0d0>, {'A': 0, 'B': 5, 'C': 2, 'D': 4, 'E': 8, 'F': 7, 'G': 6, 'H': 9, 'I': 11}),
 'B': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b160>, {'B': 0, 'A': 5, 'D': 8, 'C': 7, 'E': 12, 'F': 12, 'G': 10, 'H': 13, 'I': 16}),
 'C': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b1f0>, {'C': 0, 'A': 2, 'E': 7, 'F': 5, 'B': 7, 'D': 6, 'G': 8, 'H': 7, 'I': 9}),
 'D': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b280>, {'D': 0, 'A': 4, 'B': 8, 'E': 4, 'G': 2, 'C': 6, 'F': 7, 'H': 5, 'I': 10}),
 'E': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b310>, {'E': 0, 'A': 8, 'C': 7, 'D': 4, 'F': 3, 'G': 2, 'H': 3, 'B': 12, 'I': 7}),
 'F': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b3a0>, {'F': 0, 'C': 5, 'E': 3, 'H': 2, 'I': 4, 'A': 7, 'B': 12, 'D': 7, 'G': 5}),
 'G': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b430>, {'G': 0, 'D': 2, 'E': 2, 'H': 3, 'A': 6, 'B': 10, 'C': 8, 'F': 5, 'I': 8}),
 'H': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b4c0>, {'H': 0, 'E': 3, 'F': 2, 'G': 3, 'I': 5, 'A': 9, 'B': 13, 'C': 7, 'D': 5}),
 'I': defaultdict(<function floyd_warshall_predecessor_and_distance.<locals>.<lambda>.<locals>.<lambda> at 0x7fdd6ff8b550>, {'I': 0, 'F': 4, 'H': 5, 'A': 11, 'B': 16, 'C': 9, 'D': 10, 'E': 7, 'G': 8})}

ili preko Dijkstrinog algoritma

dict(nx.all_pairs_dijkstra_path(G3))

{'A': {'A': ['A'],
  'B': ['A', 'B'],
  'C': ['A', 'C'],
  'D': ['A', 'D'],
  'E': ['A', 'D', 'G', 'E'],
  'F': ['A', 'C', 'F'],
  'G': ['A', 'D', 'G'],
  'H': ['A', 'D', 'G', 'H'],
  'I': ['A', 'C', 'F', 'I']},
 'B': {'B': ['B'],
  'A': ['B', 'A'],
  'D': ['B', 'D'],
  'C': ['B', 'A', 'C'],
  'E': ['B', 'D', 'G', 'E'],
  'F': ['B', 'A', 'C', 'F'],
  'G': ['B', 'D', 'G'],
  'H': ['B', 'D', 'G', 'H'],
  'I': ['B', 'A', 'C', 'F', 'I']},
 'C': {'C': ['C'],
  'A': ['C', 'A'],
  'E': ['C', 'E'],
  'F': ['C', 'F'],
  'B': ['C', 'A', 'B'],
  'D': ['C', 'A', 'D'],
  'H': ['C', 'F', 'H'],
  'I': ['C', 'F', 'I'],
  'G': ['C', 'A', 'D', 'G']},
 'D': {'D': ['D'],
  'A': ['D', 'A'],
  'B': ['D', 'B'],
  'E': ['D', 'G', 'E'],
  'G': ['D', 'G'],
  'H': ['D', 'G', 'H'],
  'C': ['D', 'A', 'C'],
  'F': ['D', 'G', 'E', 'F'],
  'I': ['D', 'G', 'H', 'I']},
 'E': {'E': ['E'],
  'A': ['E', 'G', 'D', 'A'],
  'C': ['E', 'C'],
  'D': ['E', 'G', 'D'],
  'F': ['E', 'F'],
  'G': ['E', 'G'],
  'H': ['E', 'H'],
  'I': ['E', 'F', 'I'],
  'B': ['E', 'G', 'D', 'B']},
 'F': {'F': ['F'],
  'C': ['F', 'C'],
  'E': ['F', 'E'],
  'H': ['F', 'H'],
  'I': ['F', 'I'],
  'G': ['F', 'H', 'G'],
  'A': ['F', 'C', 'A'],
  'D': ['F', 'H', 'G', 'D'],
  'B': ['F', 'C', 'A', 'B']},
 'G': {'G': ['G'],
  'D': ['G', 'D'],
  'E': ['G', 'E'],
  'H': ['G', 'H'],
  'A': ['G', 'D', 'A'],
  'B': ['G', 'D', 'B'],
  'C': ['G', 'D', 'A', 'C'],
  'F': ['G', 'E', 'F'],
  'I': ['G', 'H', 'I']},
 'H': {'H': ['H'],
  'E': ['H', 'E'],
  'F': ['H', 'F'],
  'G': ['H', 'G'],
  'I': ['H', 'I'],
  'C': ['H', 'F', 'C'],
  'A': ['H', 'G', 'D', 'A'],
  'D': ['H', 'G', 'D'],
  'B': ['H', 'G', 'D', 'B']},
 'I': {'I': ['I'],
  'F': ['I', 'F'],
  'H': ['I', 'H'],
  'C': ['I', 'F', 'C'],
  'E': ['I', 'F', 'E'],
  'G': ['I', 'H', 'G'],
  'A': ['I', 'F', 'C', 'A'],
  'D': ['I', 'H', 'G', 'D'],
  'B': ['I', 'F', 'C', 'A', 'B']}}

dict(nx.all_pairs_dijkstra_path_length(G3))

{'A': {'A': 0,
  'C': 2,
  'D': 4,
  'B': 5,
  'G': 6,
  'F': 7,
  'E': 8,
  'H': 9,
  'I': 11},
 'B': {'B': 0,
  'A': 5,
  'C': 7,
  'D': 8,
  'G': 10,
  'F': 12,
  'E': 12,
  'H': 13,
  'I': 16},
 'C': {'C': 0, 'A': 2, 'F': 5, 'D': 6, 'E': 7, 'B': 7, 'H': 7, 'G': 8, 'I': 9},
 'D': {'D': 0,
  'G': 2,
  'A': 4,
  'E': 4,
  'H': 5,
  'C': 6,
  'F': 7,
  'B': 8,
  'I': 10},
 'E': {'E': 0,
  'G': 2,
  'F': 3,
  'H': 3,
  'D': 4,
  'C': 7,
  'I': 7,
  'A': 8,
  'B': 12},
 'F': {'F': 0,
  'H': 2,
  'E': 3,
  'I': 4,
  'C': 5,
  'G': 5,
  'A': 7,
  'D': 7,
  'B': 12},
 'G': {'G': 0,
  'D': 2,
  'E': 2,
  'H': 3,
  'F': 5,
  'A': 6,
  'I': 8,
  'C': 8,
  'B': 10},
 'H': {'H': 0,
  'F': 2,
  'E': 3,
  'G': 3,
  'I': 5,
  'D': 5,
  'C': 7,
  'A': 9,
  'B': 13},
 'I': {'I': 0,
  'F': 4,
  'H': 5,
  'E': 7,
  'G': 8,
  'C': 9,
  'D': 10,
  'A': 11,
  'B': 16}}

Možemo definirati funkciju FW koja će ispisati u obliku tablice pojedine korake Floyd-Warshallovog algoritma. Koje točno korake želimo ispisati, navodimo u varijabli step. Na primjer, step=[1,2,5] ako želimo ispisati prvi, drugi i peti korak algoritma, step=[3] ako želimo ispisati treći korak algoritma, step=range(6) ako želimo ispisati prvih 5 koraka, uključujući i nulti korak. Varijabla redoslijed_vrhova nam omogućuje da sami unaprijed rasporedimo vrhove u tablici; ako ništa ne navedemo, vrhovi grafa G će biti raspoređeni onako kako su raspoređeni u listi G.vertices(). Varijabla ncol određuje u koliko stupaca će biti ispisane tablice za pojedine navedene korake algoritma. Funkcija FW_html nam omogućuje ispis u obliku tablice.

def FW_html(lista,redak,stupac,korak=' '):
	lista=list(map(list,list(lista)))
	stupac=[korak]+stupac
	for k in range(len(lista)):
		lista[k]=[redak[k]]+lista[k]
	lista=[stupac]+lista
	return table(lista)

def FW(graf,step,ncol,redoslijed_vrhova=None):
    if redoslijed_vrhova==None:
        redoslijed_vrhova=graf.vertices()
    bridovi=graf.edges(labels=False)
    matrica=[[0 for j in range(len(redoslijed_vrhova))] for i in range(len(redoslijed_vrhova))]
    for i in range(len(redoslijed_vrhova)):
        for j in range(i+1,len(redoslijed_vrhova)):
            if (redoslijed_vrhova[i],redoslijed_vrhova[j]) in bridovi:
                matrica[i][j]=graf.edge_label(redoslijed_vrhova[i],redoslijed_vrhova[j])
                matrica[j][i]=graf.edge_label(redoslijed_vrhova[i],redoslijed_vrhova[j])
            elif (redoslijed_vrhova[j],redoslijed_vrhova[i]) in bridovi:
                matrica[i][j]=graf.edge_label(redoslijed_vrhova[j],redoslijed_vrhova[i])
                matrica[j][i]=graf.edge_label(redoslijed_vrhova[j],redoslijed_vrhova[i])
            else:
                matrica[i][j]=Infinity
                matrica[j][i]=Infinity
    koraci={0:deepcopy(matrica)}
    for k in range(len(redoslijed_vrhova)):
        for i in range(len(redoslijed_vrhova)):
            for j in range(len(redoslijed_vrhova)):
                matrica[i][j]=min(matrica[i][j],matrica[i][k]+matrica[k][j])
        koraci[k+1]=deepcopy(matrica)
    lista_tablica = []
    for t in step:
       lista_tablica.append(FW_html(koraci[t],redoslijed_vrhova,redoslijed_vrhova,'k='+str(t)))
    prikaz = '<table><tr style="background-color:white;">'
    for i in range(len(step)):
        prikaz = prikaz + '<td>' + html(lista_tablica[i]) + '</td>'
        if (i+1) % ncol == 0:
            prikaz = prikaz + '</tr>'
            if i+1 < len(step):
                prikaz = prikaz + '<tr style="background-color:white;">'
    if len(step) % ncol != 0:
        prikaz = prikaz + '</tr></table>'
    else:
        prikaz = prikaz + '</table>'
    return HTML(prikaz)

Nulti, treći i posljednji deveti korak Floyd-Warshallovog algoritma na težinskom grafu G1

FW(G1,step=[0,3,9],ncol=2,redoslijed_vrhova=[A,B,C,D,E,F,G,H,I])

k=0 $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ $A$ $0$ $5$ $2$ $4$ $10$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $B$ $5$ $0$ $+\infty$ $8$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $C$ $2$ $+\infty$ $0$ $+\infty$ $7$ $5$ $+\infty$ $+\infty$ $+\infty$ $D$ $4$ $8$ $+\infty$ $0$ $6$ $+\infty$ $2$ $+\infty$ $+\infty$ $E$ $10$ $+\infty$ $7$ $6$ $0$ $3$ $2$ $3$ $+\infty$ $F$ $+\infty$ $+\infty$ $5$ $+\infty$ $3$ $0$ $+\infty$ $2$ $4$ $G$ $+\infty$ $+\infty$ $+\infty$ $2$ $2$ $+\infty$ $0$ $3$ $+\infty$ $H$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $3$ $2$ $3$ $0$ $5$ $I$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $4$ $+\infty$ $5$ $0$

k=3 $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ $A$ $0$ $5$ $2$ $4$ $9$ $7$ $+\infty$ $+\infty$ $+\infty$ $B$ $5$ $0$ $7$ $8$ $14$ $12$ $+\infty$ $+\infty$ $+\infty$ $C$ $2$ $7$ $0$ $6$ $7$ $5$ $+\infty$ $+\infty$ $+\infty$ $D$ $4$ $8$ $6$ $0$ $6$ $11$ $2$ $+\infty$ $+\infty$ $E$ $9$ $14$ $7$ $6$ $0$ $3$ $2$ $3$ $+\infty$ $F$ $7$ $12$ $5$ $11$ $3$ $0$ $+\infty$ $2$ $4$ $G$ $+\infty$ $+\infty$ $+\infty$ $2$ $2$ $+\infty$ $0$ $3$ $+\infty$ $H$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $3$ $2$ $3$ $0$ $5$ $I$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $+\infty$ $4$ $+\infty$ $5$ $0$

k=9 $A$ $B$ $C$ $D$ $E$ $F$ $G$ $H$ $I$ $A$ $0$ $5$ $2$ $4$ $8$ $7$ $6$ $9$ $11$ $B$ $5$ $0$ $7$ $8$ $12$ $12$ $10$ $13$ $16$ $C$ $2$ $7$ $0$ $6$ $7$ $5$ $8$ $7$ $9$ $D$ $4$ $8$ $6$ $0$ $4$ $7$ $2$ $5$ $10$ $E$ $8$ $12$ $7$ $4$ $0$ $3$ $2$ $3$ $7$ $F$ $7$ $12$ $5$ $7$ $3$ $0$ $5$ $2$ $4$ $G$ $6$ $10$ $8$ $2$ $2$ $5$ $0$ $3$ $8$ $H$ $9$ $13$ $7$ $5$ $3$ $2$ $3$ $0$ $5$ $I$ $11$ $16$ $9$ $10$ $7$ $4$ $8$ $5$ $0$

Isprobajmo našu funkciju na dva primjera iz prezentacije

F1=Graph({"v1":{"v2":2},"v2":{"v3":3},"v3":{"v4":1}},weighted=True)

F1.plot(pos={"v1":[0,0],"v2":[1,0.5],"v3":[2,-0.5],"v4":[3,0.5]},edge_labels=True,graph_border=True,figsize=[5,4])

FW(F1,step=range(5),ncol=5)

k=0 v1 v2 v3 v4 v1 $0$ $2$ $+\infty$ $+\infty$ v2 $2$ $0$ $3$ $+\infty$ v3 $+\infty$ $3$ $0$ $1$ v4 $+\infty$ $+\infty$ $1$ $0$

k=1 v1 v2 v3 v4 v1 $0$ $2$ $+\infty$ $+\infty$ v2 $2$ $0$ $3$ $+\infty$ v3 $+\infty$ $3$ $0$ $1$ v4 $+\infty$ $+\infty$ $1$ $0$

k=2 v1 v2 v3 v4 v1 $0$ $2$ $5$ $+\infty$ v2 $2$ $0$ $3$ $+\infty$ v3 $5$ $3$ $0$ $1$ v4 $+\infty$ $+\infty$ $1$ $0$

k=3 v1 v2 v3 v4 v1 $0$ $2$ $5$ $6$ v2 $2$ $0$ $3$ $4$ v3 $5$ $3$ $0$ $1$ v4 $6$ $4$ $1$ $0$

k=4 v1 v2 v3 v4 v1 $0$ $2$ $5$ $6$ v2 $2$ $0$ $3$ $4$ v3 $5$ $3$ $0$ $1$ v4 $6$ $4$ $1$ $0$

F2=Graph({"v1":{"v2":15,"v3":5,"v4":1},"v2":{"v3":8,"v5":3},"v4":{"v5":2}},weighted=True)

F2.plot(pos={"v1":[0,3],"v2":[2,3.5],"v3":[1.2,2],"v4":[0.5,0],"v5":[4,0.3]},edge_labels=True,graph_border=True,figsize=[4,4])

FW(F2,step=range(6),ncol=3)

k=0 v1 v2 v3 v4 v5 v1 $0$ $15$ $5$ $1$ $+\infty$ v2 $15$ $0$ $8$ $+\infty$ $3$ v3 $5$ $8$ $0$ $+\infty$ $+\infty$ v4 $1$ $+\infty$ $+\infty$ $0$ $2$ v5 $+\infty$ $3$ $+\infty$ $2$ $0$	k=1 v1 v2 v3 v4 v5 v1 $0$ $15$ $5$ $1$ $+\infty$ v2 $15$ $0$ $8$ $16$ $3$ v3 $5$ $8$ $0$ $6$ $+\infty$ v4 $1$ $16$ $6$ $0$ $2$ v5 $+\infty$ $3$ $+\infty$ $2$ $0$	k=2 v1 v2 v3 v4 v5 v1 $0$ $15$ $5$ $1$ $18$ v2 $15$ $0$ $8$ $16$ $3$ v3 $5$ $8$ $0$ $6$ $11$ v4 $1$ $16$ $6$ $0$ $2$ v5 $18$ $3$ $11$ $2$ $0$
k=3 v1 v2 v3 v4 v5 v1 $0$ $13$ $5$ $1$ $16$ v2 $13$ $0$ $8$ $14$ $3$ v3 $5$ $8$ $0$ $6$ $11$ v4 $1$ $14$ $6$ $0$ $2$ v5 $16$ $3$ $11$ $2$ $0$	k=4 v1 v2 v3 v4 v5 v1 $0$ $13$ $5$ $1$ $3$ v2 $13$ $0$ $8$ $14$ $3$ v3 $5$ $8$ $0$ $6$ $8$ v4 $1$ $14$ $6$ $0$ $2$ v5 $3$ $3$ $8$ $2$ $0$	k=5 v1 v2 v3 v4 v5 v1 $0$ $6$ $5$ $1$ $3$ v2 $6$ $0$ $8$ $5$ $3$ v3 $5$ $8$ $0$ $6$ $8$ v4 $1$ $5$ $6$ $0$ $2$ v5 $3$ $3$ $8$ $2$ $0$

Kruskalov i Primov algoritam

graf=Graph({A:{B:6,D:2,E:9,S:7},B:{C:2,E:3,S:9},
            C:{E:2,F:6,S:1},D:{E:5,T:3},E:{F:7,T:9},
            F:{T:6}},weighted=True)

pozicijeGraf={A:[2,4],B:[2,2],C:[2,0],D:[4,4],E:[4,2],F:[4,0],S:[0,2],T:[6,2]}

graf.plot(pos=pozicijeGraf,edge_labels=True,graph_border=True,figsize=[5,5])

graf.min_spanning_tree(algorithm="Kruskal")

[(S, C, 1), (D, A, 2), (C, E, 2), (B, C, 2), (D, T, 3), (D, E, 5), (F, C, 6)]

graf.min_spanning_tree(algorithm="Prim_edge",starting_vertex=F)

[(F, C, 6), (S, C, 1), (C, E, 2), (B, C, 2), (D, E, 5), (D, A, 2), (D, T, 3)]

Dolje su definicije funkcija rucni_Kruskal i rucni_Prim koje nam na izlazu daju tablice kakve mi dobivamo ručnim provođenjem algoritama. Parametar opcija može imati vrijednosti 'min' ili 'max' ovisno o tome želimo li minimalno ili maksimalno razapinjuće stablo.

def rucni_Kruskal(G,opcija='min'):
    if opcija == 'min':
        bridovi=G.min_spanning_tree(algorithm="Kruskal")
    elif opcija == 'max':
        bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Kruskal")
    else:
        return "Error: postoje samo 'min' i 'max' opcija za Kruskalov algoritam"
    bridovi_stablo=list(map(lambda e: e[0:2],bridovi))
    bridovi_tezine=list(map(lambda e: e[2], bridovi))
    return table([['korak']+list(range(1,len(G))),['brid']+bridovi_stablo,['tezina']+bridovi_tezine])

rucni_Kruskal(graf)

korak	$1$	$2$	$3$	$4$	$5$	$6$	$7$
brid	$\left(S, C\right)$	$\left(D, A\right)$	$\left(C, E\right)$	$\left(B, C\right)$	$\left(D, T\right)$	$\left(D, E\right)$	$\left(F, C\right)$
tezina	$1$	$2$	$2$	$2$	$3$	$5$	$6$

rucni_Kruskal(graf,'max')

korak	$1$	$2$	$3$	$4$	$5$	$6$	$7$
brid	$\left(E, A\right)$	$\left(T, E\right)$	$\left(B, S\right)$	$\left(S, A\right)$	$\left(F, E\right)$	$\left(F, C\right)$	$\left(D, E\right)$
tezina	$9$	$9$	$9$	$7$	$7$	$6$	$5$

def rucni_Prim(G,v0,opcija='min'):
    if opcija == 'min':
        bridovi=G.min_spanning_tree(algorithm="Prim_edge",starting_vertex=v0)
    elif opcija == 'max':
        bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Prim_edge",starting_vertex=v0)
    else:
        return "Error: postoje samo 'min' i 'max' opcija za Primov algoritam"
    bridovi_stablo=list(map(lambda e: e[0:2],bridovi))
    bridovi_tezine=list(map(lambda e: e[2], bridovi))
    return table([[str(v0)+' / '+'korak']+list(range(1,len(G))),['brid']+bridovi_stablo,['tezina']+bridovi_tezine])

rucni_Prim(graf,F)

F / korak	$1$	$2$	$3$	$4$	$5$	$6$	$7$
brid	$\left(F, C\right)$	$\left(S, C\right)$	$\left(C, E\right)$	$\left(B, C\right)$	$\left(D, E\right)$	$\left(D, A\right)$	$\left(D, T\right)$
tezina	$6$	$1$	$2$	$2$	$5$	$2$	$3$

rucni_Prim(graf,F,'max')

F / korak	$1$	$2$	$3$	$4$	$5$	$6$	$7$
brid	$\left(F, E\right)$	$\left(E, A\right)$	$\left(T, E\right)$	$\left(S, A\right)$	$\left(B, S\right)$	$\left(F, C\right)$	$\left(D, E\right)$
tezina	$7$	$9$	$9$	$7$	$9$	$6$	$5$

želimo li istaknuti minimalno ili maksimalno Kruskal stablo na početnom težinskom grafu

def Kruskal_stablo(G,opcija='min',raspored_vrhova=None,lay="circular"):
    if opcija == 'min':
        bridovi=G.min_spanning_tree(algorithm="Kruskal")
    elif opcija == 'max':
        bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Kruskal")
    else:
        return "Error: postoje samo 'min' i 'max' opcija za Kruskalov algoritam"
    bridovi=map(lambda e: e[0:2], bridovi)
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={"red":bridovi},layout=laj,edge_labels=True)
    else:
        slika=G.plot(edge_colors={"red":bridovi},pos=raspored_vrhova,edge_labels=True)
    return slika

Kruskal_stablo(graf,raspored_vrhova=pozicijeGraf).show(figsize=[5,5])

Kruskal_stablo(graf,'max',raspored_vrhova=pozicijeGraf).show(figsize=[5,5])

želimo li istaknuti minimalno ili maksimalno Prim stablo na početnom težinskom grafu

def Prim_stablo(G,v0,opcija='min',raspored_vrhova=None,lay="circular"):
    if opcija == 'min':
        bridovi=G.min_spanning_tree(algorithm="Prim_edge",starting_vertex=v0)
    elif opcija == 'max':
        bridovi=G.min_spanning_tree(weight_function=lambda e: -e[2],algorithm="Prim_edge",starting_vertex=v0)
    else:
        return "Error: postoje samo 'min' i 'max' opcija za Primov algoritam"
    bridovi=map(lambda e: e[0:2], bridovi)
    if raspored_vrhova==None:
        slika=G.plot(edge_colors={"red":bridovi},layout=laj,edge_labels=True)
    else:
        slika=G.plot(edge_colors={"red":bridovi},pos=raspored_vrhova,edge_labels=True)
    return slika

Prim_stablo(graf,F,raspored_vrhova=pozicijeGraf).show(figsize=[5,5])

Prim_stablo(graf,F,'max',raspored_vrhova=pozicijeGraf).show(figsize=[5,5])

Problem trgovačkog putnika

1. primjer

TSP1=Graph({"A":{"B":5,"C":5,"D":2,"E":3,"F":5},"B":{"C":1,"D":6,"E":6,"F":5},
            "C":{"D":6,"E":6,"F":5},"D":{"E":3,"F":5},"E":{"F":2}},weighted=True)

TSP1nx=TSP1.networkx_graph()

nx.draw_circular(TSP1nx,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(TSP1nx,pos=nx.circular_layout(TSP1nx),edge_labels=nx.get_edge_attributes(TSP1nx,'weight'),
                            label_pos=0.4);

min_ciklus=TSP1.traveling_salesman_problem()
min_ciklus

min_ciklus.show(edge_labels=True)

2. primjer

TSP2=Graph({"A":{"B":4,"C":9,"D":12,"E":10,"F":3},"B":{"C":6,"D":8,"E":10,"F":6},
            "C":{"D":5,"E":9,"F":12},"D":{"E":4,"F":11},"E":{"F":7}},weighted=True)

TSP2nx=TSP2.networkx_graph()

nx.draw_circular(TSP2nx,with_labels=True,node_color='y')
nx.draw_networkx_edge_labels(TSP2nx,pos=nx.circular_layout(TSP2nx),edge_labels=nx.get_edge_attributes(TSP2nx,'weight'),
                            label_pos=0.4);

min_ciklus2=TSP2.traveling_salesman_problem()
min_ciklus2

min_ciklus2.show(edge_labels=True)