CH路径规划算法，已经基本实现整体。但在最后查找时，只能查找收缩后的节点，无法将shortcut后的节点展开输出
from bdb import Breakpoint
import sys
import queue
import time
import Constants
import ALGraph
import ArcNode
import VNode
import VData
class Constants:
INF=2*10**7
MAX_STACK_SIZE=6
maxlen = 2 * 10**7
class VNode:
def init(self,index,dist,nextvet):
self.index=index
self.dist=dist
#nextvet=VNode(index,dist)
self.next=nextvet
def getIndex(self):
return self.index
def setIndex(self,index):
self.index=index
def getDist(self):
return self.dist
def setDist(self,dist):
self.dist=dist
def getNext(self):
return self.next
def setNext(self,index,dist,next1):
self.next=VNode(index,dist,next1)
class ArcNode:
def __init__(self,name):
self.name=name
self.first=None
def getName(self):
return self.name
def setName(self,name):
self.name=name
def getFirst(self):
return self.first
def setFirst(self,first):
self.first=first
class ALGraph:
def init(self,arcNum,vetNum):
self.arcNum=arcNum
self.vetNum=vetNum
self.nodes=[]
#self.nodes.append(arcnode)
def getArcNum(self):
return self.arcNum
def getALGraph(self):
return ALGraph(self.arcNum, self.vetNum)
def setArcNum(self,arcNum):
self.arcNum=arcNum
def getVetNum(self):
return self.vetNum
def setVetNum(self,vetNum):
self.vetNum=vetNum
def getNodes(self):
return self.nodes
def setNodes(self,name):
node=ArcNode(name)
node.setFirst(VNode)
self.nodes.append(node)
class Singleton:
def init(self, arcNum,vetNum):
al=ALGraph(arcNum,vetNum)
self.graph =al
def getGraph(self):
return self.graph
def setGraph(self):
self.graph = None
class Shortcut:
def init(self, _from, _to, _dist):
self._from = _from
self._to = _to
self._dist = _dist
class QueueItem:
def init(self, d, v):
self.dist = d
self.node = v
def __lt__(self, other):
return self.dist < other.dist
def __gt__(self, other):
return self.dist > other.dist
class BuildGraph:
def init(self,n,m,adj,cost):
si=Singleton(n,m)
self.graph=si
self.n = n
self.m= m
self.INF = n * maxlen
self.adj = adj
self.cost = cost
self.bi_dist = [[self.INF] * n, [self.INF] * n]
self.visited = [False] * n
self.visited_r = [False] * n
self.workset = []
self.rank = [self.INF] * n
self.dist = [self.INF] * n
self.shortcuts = []
self.is_adding_shortcuts = False
self.node_level = [0] * n
self.max_outgoing = [0] * n
self.min_outgoing = [self.INF] * n
for i in range(0, n):
self.max_outgoing[i] = max(self.adj[0][i]) if len(self.adj[0][i]) else 0
self.min_outgoing[i] = min(self.adj[0][i]) if len(self.adj[0][i]) else self.INF
def clear_containers(self):
for v in self.workset:
self.bi_dist[0][v] = self.bi_dist[1][v] = self.INF
self.visited[v] = self.visited_r[v] = False
self.workset = []
def process(self, u, q, side):
length = len(self.adj[side][u])
for i in range(0, length):
v = self.adj[side][u][i]
if self.bi_dist[side][v] > self.bi_dist[side][u] + self.cost[side][u][i]:
self.bi_dist[side][v] = self.bi_dist[side][u] + self.cost[side][u][i] ##shortcut长度计算
q.put(QueueItem(self.bi_dist[side][v], v))
def createGraph(self):
i=1
while i <self.graph.getGraph().getArcNum():
with open('C:/Users/SAO/Desktop/CHT e s t/data/点.txt',encoding='ansi') as file:
content=file.readlines()
for line in content:
#print(line)
infos=line.split()
#print(infos)
name=infos[0]
#des=infos[1]
Nodenew=ArcNode(name)
self.graph.getGraph().getNodes().append(Nodenew)
i=i+1
i=1
while i <self.graph.getGraph().getVetNum():
with open('C:/Users/SAO/Desktop/CHT e s t/data/边.txt',encoding='ansi') as file:
content=file.readlines()
for line in content:
infos=line.split('\t')
fromm=infos[0]
to=infos[1]
dis=int(float(infos[2]))
i=i+1
fromIndex=-1
toIndex=-1
cou=0
for node in self.graph.getGraph().getNodes():
if to==node.getName():
toIndex=cou
break
cou=cou+1
cou=0
for node in self.graph.getGraph().getNodes():
if fromm==node.getName():
fromIndex=cou
break
cou=cou+1
#print(type(self.graph.getGraph().getNodes()[fromIndex]))
node1=VNode(toIndex,dis,self.graph.getGraph().getNodes()[fromIndex].getFirst())
self.graph.getGraph().getNodes()[fromIndex].setFirst(node1)
node2=VNode(fromIndex, dis, self.graph.getGraph().getNodes()[toIndex].getFirst())
self.graph.getGraph().getNodes()[toIndex].setFirst(node2)
tt=i/104.27
data22 = "\r{}%".format(tt)
print(data22, end="")
print("边ok")
for i in range(0,self.graph.getGraph().getArcNum()):
tt=i/71.31
data11 = "\r{}%".format(tt)
print(data11, end="")
for j in range(0,self.graph.getGraph().getArcNum()):
dis=self.isContact(i,j)
if dis!=Constants.INF:
self.adj[0][i].append(j)
self.cost[0][i].append(dis)
self.adj[1][j].append(i)
self.cost[1][j].append(dis)
def isContact(self,fromIndex,toIndex):
dis=Constants.INF
t=self.graph.getGraph().getNodes()[fromIndex].getFirst()
while t!=None:
if t.getIndex()==toIndex:
return t.getDist()
t=t.getNext()
return dis
def getGraph(self):
return self.graph
def witness_searches(self, s, v, limit):
self.clear_containers()
q = queue.PriorityQueue() #前向dijk
q.put(QueueItem(0, s))
self.workset.append(s)
self.dist[s] = 0
hops = 3
while hops and not q.empty():
u = q.get().node
if limit <= self.dist[u]:
break
for i in range(len(self.adj[0][u])):
w = self.adj[0][u][i]
if self.rank[w] < self.rank[v] or w == v:
continue
if self.dist[w] > self.dist[u] + self.cost[0][u][i]:
self.dist[w] = self.dist[u] + self.cost[0][u][i]
q.put(QueueItem(self.dist[w], w))
self.workset.append(w)
hops -= 1
def contracted_neighbors_and_level(self, v):
num = 0
level = 0
for n in self.adj[0][v]:
if self.rank[n] != self.INF:
num += 1
if self.node_level[n] > level:
level = self.node_level[n]
for n in self.adj[1][v]:
if self.rank[n] != self.INF:
num += 1
if self.node_level[n] > level:
level = self.node_level[n]
return num + (level + 1)/2
def update_node_level(self, v):
for n in self.adj[0][v]:
if self.node_level[n] < self.node_level[v] + 1:
self.node_level[n] = self.node_level[v] + 1
for n in self.adj[1][v]:
if self.node_level[n] < self.node_level[v] + 1:
self.node_level[n] = self.node_level[v] + 1
def contract(self, v):
start_time = time.time()
max_outgoing = self.max_outgoing[v]
min_outgoing = self.min_outgoing[v]
num_of_shortcuts = 0
shortcut_cover = set()
for i in range(len(self.adj[1][v])):
u = self.adj[1][v][i]
if self.rank[u] < self.rank[v]:
continue
limit = self.cost[1][v][i] + max_outgoing - min_outgoing
self.witness_searches(u, v, limit)
for j in range(len(self.adj[0][v])):
w = self.adj[0][v][j]
shortcut_needed = True
if self.rank[w] < self.rank[v]:
continue
for k in range(len(self.adj[1][w])):
x = self.adj[1][w][k]
if self.rank[x] < self.rank[v] or x == v:
continue
if self.cost[1][v][i] + self.cost[0][v][j] >= self.dist[x] + self.cost[1][w][k]:
shortcut_needed = False
break
if shortcut_needed:
num_of_shortcuts += 1
shortcut_cover.add(w)
shortcut_cover.add(u)
if self.is_adding_shortcuts:
self.shortcuts.append(Shortcut(u, w, self.cost[1][v][i] + self.cost[0][v][j]))
for w in self.workset:
self.dist[w] = self.INF
self.workset = []
time_cost = (time.time() - start_time)
return 2*(num_of_shortcuts - len(self.adj[1][v]) - len(self.adj[0][v])) + self.contracted_neighbors_and_level(v) + len(shortcut_cover) + time_cost*3
def add_shortcuts(self):
for shortcut in self.shortcuts:
#print("add shortcuts")
if self.max_outgoing[shortcut._from] < shortcut._dist:
self.max_outgoing[shortcut._from] = shortcut._dist
if self.min_outgoing[shortcut._from] > shortcut._dist:
self.min_outgoing[shortcut._from] = shortcut._dist
self.adj[0][shortcut._from].append(shortcut._to)
self.adj[1][shortcut._to].append(shortcut._from)
self.cost[0][shortcut._from].append(shortcut._dist)
self.cost[1][shortcut._to].append(shortcut._dist)
def remove_edges(self):
for i in range(0, self.n):
j = 0
s = len(self.adj[0][i])
while j < s:
v = self.adj[0][i][j]
if self.rank[i] > self.rank[v]:
del self.adj[0][i][j]
del self.cost[0][i][j]
s -= 1
continue
j += 1
j = 0
s = len(self.adj[1][i])
while j < s:
v = self.adj[1][i][j]
if self.rank[i] > self.rank[v]:
del self.adj[1][i][j]
del self.cost[1][i][j]
s -= 1
#print("deleted")
continue
j += 1
def preprocess(self):
ordered_nodes = queue.PriorityQueue()
for v in range(0, self.n):
ordered_nodes.put(QueueItem(self.contract(v), v))
rank_count = 0
self.is_adding_shortcuts = True
while ordered_nodes.qsize() > 1:
v = ordered_nodes.get()
v.dist = self.contract(v.node)
u = ordered_nodes.get()
if v.dist <= u.dist:
print ("impt = ", v.dist)
self.add_shortcuts()
self.rank[v.node] = rank_count
self.update_node_level(v.node)
else:
ordered_nodes.put(v)
ordered_nodes.put(u)
rank_count += 1
self.shortcuts = []
self.remove_edges()
class ShortestPath:
def init(self,buildgraph):
self.buildgraph=buildgraph
self.graph = buildgraph.graph
self.dis = [0]*buildgraph.graph.getGraph().getArcNum()
self.vis=[0]*buildgraph.graph.getGraph().getArcNum()
def getPos(self, name):
pos=-1
for i in range(0,self.graph.getGraph().getArcNum()):
if name == self.graph.getGraph().getNodes()[i].getName():
pos=i
break
return pos
def modified_dijkstra(self, source, des):
s=self.getPos(source)
t=self.getPos(des)
forward_pred=[]
backward_pred=[]
forward_min_dist={}
forward_min_dist[s]=0
backward_min_dist={}
backward_min_dist[t]=0
shortpath=[]
shortpath_name=[]
shortpath.append(s)
shortpath_name.append(self.graph.getGraph().getNodes()[s].getName())
print(shortpath)
print(shortpath_name)
for i in range(0,self.graph.getGraph().getArcNum()):
if i==s:
self.dis[i]=0
else:
self.dis[i]=s
self.buildgraph.clear_containers()
estimate = self.buildgraph.INF
q = queue.PriorityQueue() #前向dijk算法
q_r = queue.PriorityQueue() #后向dijk算法
q.put(QueueItem(0, s))
q_r.put(QueueItem(0, t))
self.buildgraph.bi_dist[0][s] = 0 #最短路径=D(s,u)+D(u,t)
self.buildgraph.bi_dist[1][t] = 0
while not q.empty() or not q_r.empty():
if not q.empty():
u = q.get().node
if self.buildgraph.bi_dist[0][u] <= estimate:
self.buildgraph.process(u, q, 0)
self.buildgraph.workset.append(u)
self.buildgraph.visited[u] = True
if self.buildgraph.visited_r[u] and self.buildgraph.bi_dist[0][u] + self.buildgraph.bi_dist[1][u] < estimate:
estimate = self.buildgraph.bi_dist[0][u] + self.buildgraph.bi_dist[1][u] #预计距离 双向查询距离相加
if not q_r.empty():
u = q_r.get().node
if self.buildgraph.bi_dist[1][u] <= estimate:
self.buildgraph.process(u, q_r, 1)
self.buildgraph.workset.append(u)
self.buildgraph.visited_r[u] = True
if self.buildgraph.visited[u] and self.buildgraph.bi_dist[0][u] + self.buildgraph.bi_dist[1][u] < estimate:
shortpath.append(u)
print(shortpath)
shortpath_name.append(self.graph.getGraph().getNodes()[u].getName())
print(shortpath_name)
breakpoint()
estimate = self.buildgraph.bi_dist[0][u] + self.buildgraph.bi_dist[1][u]
shortpath.append(t)
shortpath_name.append(self.graph.getGraph().getNodes()[t].getName())
print(shortpath)
print(shortpath_name)
breakpoint()
return -1 if estimate == Constants().INF else estimate
def getPos(self,name):
pos=-1
for i in range(0,self.graph.getGraph().getArcNum()):
if name==self.graph.getGraph().getNodes()[i].getName():
pos=i
break
return pos
def getLength(self,fromIndex,toIndex):
t=self.graph.getGraph().getNodes()[fromIndex].getFirst()
print("t",t)
breakpoint()
length=Constants.INF
print("length",length)
breakpoint()
while t!=None:
if t.getIndex()==toIndex:
print("t:",t)
breakpoint()
length=t.getDist()
print("length",length)
breakpoint()
break
t=t.getNext()
return length
def getname(self,s,t):
shortpath=[]
for node in range(self.modified_dijkstra(s,t)):
shortpath.append(self.graph.getGraph().getNodes()[node].getName())
return shortpath
def readl():
return map(int, sys.stdin.readline().split())
if name == 'main':
start_time = time.time()
print('cin:')
n=7131
m=10427
adj = [[[] for _ in range(n)], [[] for _ in range(n)]]
cost = [[[] for _ in range(n)], [[] for _ in range(n)]]
构建图结构初始化
ch = BuildGraph(n,m,adj,cost)
根据点、边信息修改图结构
ch.createGraph()
CH预处理部分 进行shortcut替换
ch.preprocess()
print("Ready")
print("preprocessing took %s seconds ---" % (time.time() - start_time))
start_time2=time.time()
sys.stdout.flush()
输入查询
s='呼玛路'
t='泥城河桥'
生成最短路径
pa=ShortestPath(ch)
print("pa",pa)
breakpoint()
print(str(pa.modified_dijkstra(s,t)))
print("ShortPath finding took %s seconds ---" % (time.time() - start_time2))
能帮忙看下优化下吗可提供完整代码和数据 可加V或者Q 可给钱
