题解 | #单源最短路#

这个题目的测试用例是不全面的，应该要加上优先队列去判断
7,7,[[1,3,2],[1,4,5],[2,5,1],[3,2,1],[3,5,4],[4,5,5],[6,7,5]]

import sys
class Solution:
    def findShortestPath(self, n, m, graph):

        # 创建一个表示图的字典
        dic = {}
        for i in range(1,n+1):
            dic[i] = {}

        # 创建图
        for v in graph:
            if v[1] in dic[v[0]]:  # 由于存在重边，所以需要加一重判断
                dic[v[0]][v[1]] = min(v[2], dic[v[0]][v[1]])
            else:
                dic[v[0]][v[1]] = v[2]
        #print(dic)

        #构建表示dst属性的列表
        length = len(dic)
        dst = []
        for i in range(1,length+1):
            dst.append([sys.maxsize,i])          
        dst[0] = [0,1]
        #print(dst)  
        pq = PriorityQueue()
        pq.buildHeap(dst) 
        #print(pq.heapArray)
        while not pq.isEmpty():  
            i = pq.delMin()
            #print(i)
            for connection in dic[i]:
               # print(connection)
                #print(dst[connection-1][0])
                dst[connection-1][0] = min(dst[connection-1][0],dst[i-1][0] + dic[i][connection])
                pq.decreaseKey(dst[connection-1][1],dst[connection-1][0])
            dst[i-1][0] = dst[i-1][0] if dst[i-1][0]!=sys.maxsize else -1  #判断节点是否从初始节点可达
        return dst[-1][0]

#系统不带优先队列
class PriorityQueue:
    def __init__(self):
        self.heapArray = [(0,0)]
        self.currentSize = 0

    def buildHeap(self,alist):
        self.currentSize = len(alist)
        self.heapArray = [(0,0)]
        for i in alist:
            self.heapArray.append(i)
        i = len(alist) // 2            
        while (i > 0):
            self.percDown(i)
            i = i - 1

    def percDown(self,i):
        while (i * 2) <= self.currentSize:
            mc = self.minChild(i)
            if self.heapArray[i][0] > self.heapArray[mc][0]:
                tmp = self.heapArray[i]
                self.heapArray[i] = self.heapArray[mc]
                self.heapArray[mc] = tmp
            i = mc

    def minChild(self,i):
        if i*2 > self.currentSize:
            return -1
        else:
            if i*2 + 1 > self.currentSize:
                return i*2
            else:
                if self.heapArray[i*2][0] < self.heapArray[i*2+1][0]:
                    return i*2
                else:
                    return i*2+1
    def percUp(self,i):
        while i // 2 > 0:
            if self.heapArray[i][0] < self.heapArray[i//2][0]:
                tmp = self.heapArray[i//2]
                self.heapArray[i//2] = self.heapArray[i]
                self.heapArray[i] = tmp
            i = i//2
    def add(self,k):
        self.heapArray.append(k)
        self.currentSize = self.currentSize + 1
        self.percUp(self.currentSize)

    def delMin(self):
        retval = self.heapArray[1][1]
        self.heapArray[1] = self.heapArray[self.currentSize]
        self.currentSize = self.currentSize - 1
        self.heapArray.pop()
        self.percDown(1)
        return retval

    def isEmpty(self):
        if self.currentSize == 0:
            return True
        else:
            return False

    def decreaseKey(self,val,amt):
        # this is a little wierd, but we need to find the heap thing to decrease by
        # looking at its value
        done = False
        i = 1
        myKey = 0
        while not done and i <= self.currentSize:
            if self.heapArray[i][1] == val:
                done = True
                myKey = i
            else:
                i = i + 1
        if myKey > 0:
            self.heapArray[myKey] = (amt,self.heapArray[myKey][1])
            self.percUp(myKey)

    def __contains__(self,vtx):
        for pair in self.heapArray:
            if pair[1] == vtx:
                return True
        return False