-
Notifications
You must be signed in to change notification settings - Fork 0
/
floyd.py
50 lines (46 loc) · 1.35 KB
/
floyd.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
from copy import deepcopy
import networkx as nx
import matplotlib.pyplot as plt
" > Funciones"
def Floydwarshall(graph):
matrizfloyd=deepcopy(graph)
V=len(graph)
for k in range(V):
for i in range(V):
for j in range(V):
aux=matrizfloyd[i][k]+matrizfloyd[k][j]
if (matrizfloyd[i][j]>aux):
matrizfloyd[i][j]=aux
return matrizfloyd
def imprimir(graph):
for i in range(len(graph)):
for j in range(len(graph[i])):
print(graph[i][j], " , ")
print("")
def pedirdatos():
INF = 99999
g=nx.DiGraph()
print("Crear Matriz De Adyacencia")
V= int(input("Cantidad de vertices: "))
graph = []
for v1 in range(V):
graph.append([])
print(graph)
for v2 in range(V):
if v1 == v2:
graph[v2].append(0)
else:
print("Distancia de: ", v1+1, "-", v2+1, " : ")
aux=input()
if aux == '':
distancia = INF
else:
distancia = int(aux)
g.add_edge(v1,v2,weight=aux)
graph[v1].append(distancia)
return graph,g
matriz,g=pedirdatos()
matriz=Floydwarshall(matriz)
print(matriz)
nx.draw(g,with_labels=True)
plt.show()