import MapCreater
import OneRoadMapCreater
import copy
import random
import operator
import InputCtrl
def MinTransferDijkstra(StartSite, EndSite):
if StartSite == EndSite:
return 0, [], []
if StartSite not in OneRoadMapCreater.SiteDic:
print("起始点不存在")
return -1, [], []
if EndSite not in OneRoadMapCreater.SiteDic:
print("终止点不存在")
return -1, [], []
StartSiteIndex = OneRoadMapCreater.SiteDic[StartSite]
EndSiteIndex = OneRoadMapCreater.SiteDic[EndSite]
DijkstraArr = copy.deepcopy(OneRoadMapCreater.HeadSiteArr)
minlen = float("inf")
BusIdMaps = []
RouteMaps = []
is_continue = 10
while is_continue:
RouteMap = [[float("inf") for col in range(500)] for row in range(500)] # 存储最短路径,之后倒序查找可以回溯到起始点
valuequeue = [] #权值队列,存储pair(index, value)
BusIdMap = [[[] for col in range(500)] for row in range(500)] #保存车站路径,之后倒序查找可以回溯到起始点
for i, site in enumerate(DijkstraArr[StartSiteIndex]):
if site < 10000:
pair = [i, site, StartSiteIndex]
valuequeue.append(pair)
DijkstraArr[i][StartSiteIndex] = float("inf") #无向边,从正向走过去就不要走回来了
else:
continue #如果不连通(权值是无穷大)则跳过
#初步找到了所有和StartSite相连的点,建立邻接路径矩阵,每次保存最短路径,之后可以倒序输出。
while(len(valuequeue) > 0):#非空,先将队列排序,按照value递增排序,每次弹出队列头。
sorted(valuequeue, key=lambda t: t[1]) #按照value对valuequeue中的pair进行排序
#valuequeue中最小值可能不止一个,随机返回一个最小值
minline = []
min_in_minline = valuequeue[0][1] #valuequeue头上的一定是最小的
for tmin in valuequeue:
if tmin[1] == min_in_minline:
minline.append(tmin)
else:
break
random.shuffle(minline)
[tindex, tvalue, tparent] = valuequeue.pop(valuequeue.index(minline.pop(0))) #释放队列头,即权值最小的节点
RouteMap[tparent][tindex] = tvalue #这一条路径已经确定,记录下来
BusIdMap[tparent][tindex].extend(OneRoadMapCreater.BusIdArr[tparent][tindex]) #保存路线站点
#DijkstraArr[tparent][tindex] = float("inf")
if tindex == EndSiteIndex: #这样就找到了
#return tvalue, RouteMap, BusIdMap
if minlen >= tvalue:
minlen = tvalue
# for eachroute in RouteMaps:
# if doublelist_equal(eachroute, RouteMap):
# break
# else:
RouteMaps.append(RouteMap)
BusIdMaps.append(BusIdMap)
is_continue -= 1
break
else:
is_continue = 0
return minlen, RouteMaps, BusIdMaps
else: #这样就还没找到
temparr = [] #暂时保存新扩展的节点
for i, tsite in enumerate(DijkstraArr[tindex]):
if tsite < 10000:
tpair = [i, tsite + tvalue, tindex] #因为是在tindex对应的节点上扩展的,所以权值应该是tindex的权值+本身的权值
temparr.append(tpair)
DijkstraArr[i][tindex] = float("inf")
while(len(temparr) > 0): #用新扩展的节点更新dijkstra邻接矩阵路径代价
[newindex, newvalue, newparent] = temparr.pop()
for one in valuequeue:
if newindex == one[0]: #如果扩展到了已经存在的节点,就更新值
if one[1] > newvalue:
one[1] = newvalue
break
else: #如果是新扩展的,就添加进入队列中
valuequeue.append([newindex, newvalue, newparent])
else:
#print("没有路径")
print(minlen)
return minlen, RouteMaps, BusIdMaps
return minlen, RouteMaps, BusIdMaps
def MinDistanceDijkstra(StartSite, EndSite):
if StartSite == EndSite:
return 0, [], []
if StartSite not in MapCreater.SiteDic:
print("起始点不存在")
return -1, [], []
if EndSite not in MapCreater.SiteDic:
print("终止点不存在")
return -2, [], []
StartSiteIndex = MapCreater.SiteDic[StartSite]
EndSiteIndex = MapCreater.SiteDic[EndSite]
DijkstraArr = copy.deepcopy(MapCreater.HeadSiteArr)
minlen = float("inf")
BusIdMaps = []
RouteMaps = []
is_continue = 10
while is_continue:
RouteMap = [[float("inf") for col in range(500)] for row in range(500)] # 存储最短路径,之后倒序查找可以回溯到起始点
valuequeue = [] #权值队列,存储pair(index, value)
BusIdMap = [[[] for col in range(500)] for row in range(500)] #保存车站路径,之后倒序查找可以回溯到起始点
for i, site in enumerate(DijkstraArr[StartSiteIndex]):
if site < 10000:
pair = [i, site, StartSiteIndex]
valuequeue.append(pair)
DijkstraArr[i][StartSiteIndex] = float("inf") #无向边,从正向走过去就不要走回来了
else:
continue #如果不连通(权值是无穷大)则跳过
#初步找到了所有和StartSite相连的点,建立邻接路径矩阵,每次保存最短路径,之后可以倒序输出。
while(len(valuequeue) > 0):#非空,先将队列排序,按照value递增排序,每次弹出队列头。
sorted(valuequeue, key=lambda t: t[1]) #按照value对valuequeue中的pair进行排序
#valuequeue中最小值可能不止一个,随机返回一个最小值
minline = []
min_in_minline = valuequeue[0][1] #valuequeue头上的一定是最小的
for tmin in valuequeue:
if tmin[1] == min_in_minline:
minline.append(tmin)
else:
break
random.shuffle(minline)
[tindex, tvalue, tparent] = valuequeue.pop(valuequeue.index(minline.pop(0))) #释放队列头,即权值最小的节点
RouteMap[tparent][tindex] = tvalue #这一条路径已经确定,记录下来
BusIdMap[tparent][tindex].extend(MapCreater.BusIdArr[tparent][tindex]) #保存路线站点
#DijkstraArr[tparent][tindex] = float("inf")
if tindex == EndSiteIndex: #这样就找到了
#return tvalue, RouteMap, BusIdMap
if minlen >= tvalue:
minlen = tvalue
# for eachroute in RouteMaps:
# if doublelist_equal(eachroute, RouteMap):
# break
# else:
RouteMaps.append(RouteMap)
BusIdMaps.append(BusIdMap)
is_continue -= 1
break
else:
is_continue = 0
return minlen, RouteMaps, BusIdMaps
else: #这样就还没找到
temparr = [] #暂时保存新扩展的节点
for i, tsite in enumerate(DijkstraArr[tindex]):
if tsite < 10000:
tpair = [i, tsite + tvalue, tindex] #因为是在tindex对应的节点上扩展的,所以权值应该是tindex的权值+本身的权值
没有合适的资源?快使用搜索试试~ 我知道了~
温馨提示
【资源介绍】 基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip 基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip 基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip 【说明】 该项目是个人毕设项目,答辩评审分达到95分,代码都经过调试测试,确保可以运行!欢迎下载使用,可用于小白学习、进阶。 该资源主要针对计算机、通信、人工智能、自动化等相关专业的学生、老师或从业者下载使用,亦可作为期末课程设计、课程大作业、毕业设计等。 项目整体具有较高的学习借鉴价值!基础能力强的可以在此基础上修改调整,以实现不同的功能。 欢迎下载交流,互相学习,共同进步!
资源推荐
资源详情
资源评论
收起资源包目录
基于python实现的公交换成系统源码(求解最短路径+最少换乘问题)带GUI界面.zip (62个子文件)
ReadExcel.py 2KB
.gitattributes 66B
MapCreater.py 2KB
公交.xlsx 12KB
QtUi
ui_infowind.py 6KB
InfoWind.ui 3KB
WorkingWind.ui 5KB
ui_main.py 4KB
WorkingWind.ui.autosave 5KB
main.ui 2KB
ui_workingwind.py 10KB
.idea
.name 7B
BusTransportSystem.iml 385B
other.xml 233B
misc.xml 185B
inspectionProfiles
profiles_settings.xml 174B
modules.xml 270B
.gitignore 182B
runConfigurations
PyUI.xml 1KB
PyUi2.xml 1KB
MindSpore.iml 296B
图片
Map创建.drawio 12KB
信息展示2.png 38KB
邻接表.png 2KB
公交换乘.png 22KB
信息展示.png 27KB
公交路径.png 49KB
公交线路.png 87KB
公交换乘.drawio 5KB
Map创建.png 58KB
InputCtrl.py 1KB
ͼƬ
Dijkstra.png 76KB
GitHub.png 56KB
Dijkstra.drawio 9KB
Calculator.py 24KB
OneRoadMapCreater.py 3KB
ExcelReader.py 878B
PyUi2.py 7KB
测试.xlsx 9KB
已废弃
ui_infowind.py 6KB
Calculator-备份2.py 5KB
正向.csv 5.5MB
ui_main.py 4KB
反向.csv 5.07MB
Calculator备份.py 3KB
Calculator-备份3.py 4KB
PyUI.py 430B
ui_workingwind.py 10KB
__pycache__
Calculator.cpython-38.pyc 10KB
MapCreater.cpython-310.pyc 1KB
MapCreater.cpython-38.pyc 2KB
SiteMapClass.cpython-39.pyc 911B
ExcelReader.cpython-310.pyc 844B
InputCtrl.cpython-38.pyc 1KB
MapCreater.cpython-39.pyc 1KB
ExcelReader.cpython-39.pyc 825B
OneRoadMapCreater.cpython-38.pyc 2KB
ExcelReader.cpython-38.pyc 884B
.ipynb_checkpoints
Untitled-checkpoint.ipynb 72B
Untitled1-checkpoint.ipynb 585B
MainWind.py 17B
公交换乘.drawio 5KB
共 62 条
- 1
资源评论
- m0_741663112024-01-04支持这个资源,内容详细,主要是能解决当下的问题,感谢大佬分享~
- FluoxitineYL2023-12-01资源不错,很实用,内容全面,介绍详细,很好用,谢谢分享。
- tansk123062023-11-11资源不错,内容挺好的,有一定的使用价值,值得借鉴,感谢分享。Make程序设计2023-11-24嗯嗯,客气了,互相学习1
Make程序设计
- 粉丝: 5638
- 资源: 3568
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功