Label Correcting Algorithm(Python实现)

　

correcting

代码：

dequeue版：

from collections import deque
import numpy as np
class edge:                       #定义边
    def __init__(self,start,end,cost):
        self.Start=start
        self.End=end
        self.Cost=cost
inf=2147483647
n=int(input("n="))                #n是点数
m=int(input("m="))                #m是边数
E=[]                              #存图中所有的边
Edge=np.zeros((n+1,n+1),dtype=int)#邻接表/前向星
dist=np.empty((n+1),dtype=int)    #记录当前最短路长度
vis=np.zeros((n+1),dtype=int)     #0表示未入队，1表示在队中，-1表示已出队
pre=np.zeros((n+1),dtype=int)     #记录前一个节点
Q=deque()
'''
def TestEdge():                   #邻接表测试函数
    for i in range(1,n+1):
        for j in range(1,Edge[i,0]+1):
            print(i,E[Edge[i,j]].End,E[Edge[i,j]].Cost)
'''
def FindTheWay(x):                #递归输出路径
    if pre[x]>0:
        FindTheWay(pre[x])
        print(pre[x],"->",end='')

for i in range(m):
    start,end,cost=map(int,input().split())  #读起点终点花费
    E.APPend(edge(start,end,cost))           #加入图中，存边
    Edge[start][Edge[start][0]+1]=i          #记录start节点发出一条新边
    Edge[start][0]+=1

for i in range(n+1):
    dist[i]=inf
s=int(input("起点:"))
t=int(input("终点:"))
dist[s]=0
Q.append(s)
vis[s]=1;
while len(Q)>0:
    tmp=int(Q.popleft())
    vis[tmp]=-1
    length=Edge[tmp][0]
    for i in range(1,length+1):
        index=Edge[tmp][i]
        to=E[index].End
        if dist[to]>dist[tmp]+E[index].Cost:
            dist[to]=dist[tmp]+E[index].Cost
            pre[to]=tmp
            if vis[to]==-1: Q.appendleft(to)
            else: Q.append(to)
            vis[to]=1
if dist[t]<inf:
    print("最短路长度=",dist[t])
    print("最短路径为:",end='')
    FindTheWay(t)
    print(t)
else: print("无法到达")

sequence list版：

import numpy as np
inf=2147483647
n=int(input("n="))                #n是点数
m=int(input("m="))                #m是边数
class edge:                       #定义边
    def __init__(self,start,end,cost):
        self.Start=start
        self.End=end
        self.Cost=cost
class SequenceList:                    #定义队列
    vis=np.zeros((n+1),dtype=int)
    def __init__(self):
        self.right=int(0)
        self.vis[0]=inf
    def AddToQ(self,x):                #加入队尾
        self.vis[self.right]=x
        self.vis[x]=inf
        self.right=x
    def AddToQLeft(self,x):            #加入队首
        self.vis[x]=self.vis[0]
        self.vis[0]=x
    def pop(self):                     #取队首元素
        tmp=self.vis[0]
        self.vis[0]=self.vis[tmp]
        self.vis[tmp]=-1
        if tmp==self.right: self.right=0
        return tmp
    def empty(self):                   #判断队列是否为空
        if self.vis[0]==inf: return 1  #队列为空，返回真(1)
        else: return 0                 #队列非空，返回假(0)

E=[]                              #存图中所有的边
Q=SequenceList()                  #SequenceList实例化
Edge=np.zeros((n+1,n+1),dtype=int)#邻接表/前向星
dist=np.empty((n+1),dtype=int)    #记录当前最短路长度
pre=np.zeros((n+1),dtype=int)     #记录前一个节点

def FindTheWay(x):                #递归输出路径
    if pre[x]>0:
        FindTheWay(pre[x])
        print(pre[x],"->",end='')

for i in range(m):
    start,end,cost=map(int,input().split())  #读起点终点花费
    E.append(edge(start,end,cost))           #加入图中，存边
    Edge[start][Edge[start][0]+1]=i          #记录start节点发出一条新边
    Edge[start][0]+=1

for i in range(n+1):
    dist[i]=inf
s=int(input("起点:"))
t=int(input("终点:"))
dist[s]=0
Q.AddToQ(s)
while Q.empty()==0:
    tmp=Q.pop()
    length=Edge[tmp][0]
    for i in range(1,length+1):
        index=Edge[tmp][i]
        to=E[index].End
        if dist[to]>dist[tmp]+E[index].Cost:
            dist[to]=dist[tmp]+E[index].Cost
            pre[to]=tmp
            if Q.vis[to]==-1: Q.AddToQLeft(to)
            else: Q.AddToQ(to)
if dist[t]<inf:
    print("最短路长度=",dist[t])
    print("最短路径为:",end='')
    FindTheWay(t)
    print(t)
else: print("无法到达")

样例：

输入：
n=4

m=4

1 2 1

2 3 2

2 4 10

3 4 5

起点:1

终点:4


输出：
最短路长度= 8
最短路径为:1 ->2 ->3 ->4

相关阅读

动态规划挖金矿问题——python实现

最近在复习动态规划问题，在处理挖金矿问题的时候发现网上以python实现的代码很少，于是自己整理一份。 问题描述：漫画图解 公式和讲解

python实现K_mean算法

# encoding: utf-8 ''' #!/usr/bin/env python @author: yudian @contact: [email protected] @file: k_means.py @time: 2018/12

决策树算法及python实现

1.什么是决策树 / 判定树（Decision Tree）? 决策树是一个类似于流程图的树结构：其中，每个内部结点表示在一个属性上的测试，每个分支代表

python实现opencv学习十四：图像二值化

图像二值化：基于图像的直方图来实现的，0白色 1黑色一：全局# -*- coding=GBK -*- import cv2 as cv import numpy as np #图像二值

python实现自动定时给女朋友发手机短信，每天一个笑话！

Python 的概念 大四的生活就是这么无聊，我琢磨着也学了这么多东西了，为啥不能用自己的知识来给生活找点乐子呢？我想反正每天都要给T