Не удается получить путь кратчайшего пути со случайным вводом - PullRequest
0 голосов
/ 01 июня 2019

Я хочу получить кратчайший путь каждого узла (этот узел, я думал, что это одно место, где турист может посетить), и я рандомизировал, открыт узел или нет, когда он открыт, когда он закрыт.При этом, если я введу случайный номер узла из 3,9, как показано ниже, и если начальная точка становится равной 0, она просто останавливается там.Я думаю, что нам нужно больше ограничений с начальной точкой.

from collections import defaultdict
import math
from heapq import heapify, heappush, heappop
import random

# utility: priority queue
class Pq:
def __init__(self):
    self.queue = []

def __str__(self):
    return str(self.queue)

def insert(self, item):
    heappush(self.queue, item)

def extract_min(self):
    return heappop(self.queue)[1]

def update_priority(self, key, priority):
    for v in self.queue:
        if v[1] == key:
            v[0] = priority
    heapify(self.queue)

def empty(self):
    return len(self.queue) == 0

# utility: Graph
class Graph:
def __init__(self, vertices):
    self.V = vertices
    self.graph = defaultdict(lambda: [])

def add_edge(self, v, u, w):
    self.graph[v].append((u, w))

def __str__(self):
    result = ''
    for v in self.V:
        result += f'{v}: {str(self.graph[v])}, \n'
    return result

def dijkstra(graph, s, time):
Q = Pq() # priority queue of vertices
         # [ [distance, vertex], ... ]
d = dict.fromkeys(graph.V, math.inf) # distance pair
                               # will have default value of Infinity
pi = dict.fromkeys(graph.V, None) # map of parent vertex
                                  # useful for finding shortest path
Rhour = dict.fromkeys(graph.V, math.inf)


# initialize

d[s] = 0
Rhour1 =time
Rhour[s] = Rhour1
print(Rhour1)
sday = today
print(sday)
OP=[]
CCL=[]
OC=[]
OP.extend(opentime[sday])
print(OP)
CCL.extend(closetime[sday])
print(CCL)
OC.extend(dayopen[sday])
print(OC)



# update priority if prior path has larger distance
def relax(u, v, w):
    print(u)
    print(Q)
    if OC[u]==0 :
        if d[v]<d[u]+w:
            print(d[u])
            print(w)
            d[v]=d[u]+w
            Rhour1=Rhour[s]
            Rhour[u]=Rhour1
        else :
            d[v]

    else:
        print(OC[u]!=0)
        No=d[u]+w+stay[u]
        print(No)
        j=pi[v]
        print(j)
        Rhour1=Rhour[s]+(No/60)
        print(Rhour1)
        print(No)

        if d[v]>No and CCL[u]>Rhour1>OP[u]:
            d[v] = No
            Rhour[u]=Rhour1

        elif d[v]<d[u]+w:
            d[v]=d[u]+w
            Rhour[u]=Rhour1


    Q.update_priority(v, d[v])
    pi[v] = u
    print(Q)



# initialize queue
for v in graph.V:
    Q.insert([d[v], v])

while not Q.empty():
    u = Q.extract_min()
    for v, w in graph.graph[u]:
        relax(u, v, w)
return d, pi, Rhour



def shortest_path(s, t):
d, pi, Rhour= dijkstra(g, s, time)
path = [t]
current = t
print(path)


    # if parent pointer is None,
    # then it's the source vertex
while pi[current]:
      path.insert(0, pi[current])
            # set current to parent
      current = pi[current]

if s not in path:
    return f'unable to find shortest path staring from "{s}" to "{t}"'

return f'{" > ".join(path), d[t]}'

#which date is today, when is the starting time => randomize
today = random.choice(list(range(0,7)))
print(today)
stt = random.choice(list(range(9,13)))
print(stt)
time=stt

#staying time random

number = 10 #관광지 개수

sstay=list(range(30,90))
stay = [random.choice(sstay)for _ in range(number)]
print(stay)

#open_or_not, open, close time

dayopen=[[random.randrange(0,2) for _ in range(number)] for _ in
range(7)]
opentime=[[random.randrange(9,12) for _ in range(number)]for _ in
range(7)]
closetime=[[random.randrange(17,21) for _ in range(number)]for _ in
range(7)]




#node_and_edges
two_d_list = [[0 for _ in range(number)] for _ in range(number)]


node = list(range(0,number))


eedge=list(range(20,50))

for k in node:
    for j in node:
        if k==j:
        two_d_list[k][j]=0
    else:
        a=random.choice(eedge)
        two_d_list[k][j]=a

print(two_d_list)


g = Graph(node)

for a in node:
    for b in node:
        if not a==b:
        g.add_edge(a,b,two_d_list[a][b])
    else :
        g.add_edge(a,b,0)

shortest_path(6,8)
...