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的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip
共62个文件
py:18个
pyc:10个
png:9个
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 73 浏览量
2024-04-10
00:23:07
上传
评论
收藏 2.23MB ZIP 举报
温馨提示
【资源说明】 1、该资源包括项目的全部源码,下载可以直接使用! 2、本项目适合作为计算机、数学、电子信息等专业的课程设计、期末大作业和毕设项目,作为参考资料学习借鉴。 3、本资源作为“参考资料”如果需要实现其他功能,需要能看懂代码,并且热爱钻研,自行调试。 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip 基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip
资源推荐
资源详情
资源评论
收起资源包目录
基于python的公交换乘系统源码+示例图片(求解最短路径,最少换乘问题).zip (62个子文件)
code_20105
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
Dijkstra.png 76KB
信息展示2.png 38KB
邻接表.png 2KB
公交换乘.png 22KB
GitHub.png 56KB
信息展示.png 27KB
公交路径.png 49KB
公交线路.png 87KB
Dijkstra.drawio 9KB
公交换乘.drawio 5KB
Map创建.png 58KB
InputCtrl.py 1KB
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
资源评论
土豆片片
- 粉丝: 1540
- 资源: 5641
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功