I'm using this site for the first time I can find the shortest time while studying, but I can't find the route, so I'm asking you a question
INF=int(1e9)
def print_d(x=0):
if x:
print (shortest distance =') after passing through the f'=[{n+1}] node
else:
print ('=Initial value before search =')
for i in range(len(d)):
for j in range(len(d)):
if d[i][j]==INF:
print(' ∞', end=' ')
else:
print(f'{d[i][j]:2}', end=' ')
print()
node=int(input('number of nodes input:'))
d=[[INF]*node for i in range(node)]
for i in range(node):
for j in range(node):
if i == j:
d[i][j] = 0
else:
line = int (enter the distance of input(f'{i+1}→{j+1} (0 if none):')
if line:
d[i][j] = line
print_d()
Please tell me how to express the coding on the ash like the shortest path below.
python
It's not Floyd Walsall, but it's a code for finding the Dijkstra route that I did for my assignment. I hope it's usefulYo
from math import inf
from collections import defaultdict
def dijkstra_path(W):
V = len(W)
F = defaultdict(list) # The set of joints that make up the shortest path
P = defaultdict(list) # The shortest path set of each node
S = defaultdict(list) # The shortest set of distances up to each node
path = [] # List to store shortest paths
touch = [0] * V
length = [W[0][i] for i in range(V)]
length[0] = -1
for _ in range(V-1):
min = inf
for i in range(V):
if (0 < length[i] < min):
min = length[i]
vnear = i
F[touch[vnear]].append(vnear)
t=0
k=[]
if len(path) == 0:
path.append([touch[vnear]+1])
eliflen (F[touch[vnear]) > 1: # When going from one bar to multiple bars
k = [] # Copy path list
for i in path:
k.append(i)
For iin k: # When creating a new path, use k copied so that it is not created indefinitely
for j in range(len(i)):
if (i[j] == touch[vnear]+1) & (t != 1):
t = 1 # Prevents duplicate paths from being created
path.append(i[0:j+1])
ift!=1: # Add a bar to an existing path if you have not created a new path
for i in path:
for j in range(len(i)):
if i[j] == touch[vnear]+1:
i.insert(j+1, vnear+1)
else: # Add a bar to the newly created path
for i in range(len(k), len(path)):
for j in range(len(path[i])):
if path[i][j] == touch[vnear]+1:
path[i].insert(j+1, vnear+1)
for i in range(V):
if (length[vnear] + W[vnear][i] < length[i]):
length[i] = length[vnear] + W[vnear][i]
touch[i] = vnear
S[vnear]append(length[vnear]) #Shortest Distance Storage
length[vnear] = -1
for i in range(V-1):
P[i+2].append(-1)
for k in P:
for i in path:
for j in range(len(i)):
if (k == i[j]) & (P[k][0] == -1):
P[k].append(str(i[:j+1]).strip('[]'))
P[k].remove(-1)
for i in P:
print("Shortest path to V{0} (distance: {1}): V{2}".format(i, str(S[i-1]).strip('[]'),'->V'.join(P[i][0].split(', '))))
W = [[0, 7, 4, 6, 1],
[inf, 0, inf, inf, inf],
[inf, 2, 0, 5, inf],
[inf, 3, inf, 0, inf],
[inf, inf, inf, 1, 0]]
dijkstra_path(W)
© 2024 OneMinuteCode. All rights reserved.