如何优化这个python程序，使它快0.20.1秒？Dijkstra算法

Question

import time
class DJ:
    def __init__(self, roads, n):
        self.roads, self.n=roads,n

    #Dijkstra with mod for a pathway from vertex a to c 
    #returns dist of a to all points if arg c is 0    
    def dis(self,a,c):
        spset,dist,prev,path,k=[],['d'],['d'],[],[]

        dist.extend([float("inf")]*self.n)
        prev.extend([0]*self.n)
        dist[a]=0

        if a==c:
            return [a]

        while len(spset)!=self.n:
            k=[dist[m] for m in range(1,self.n+1) if m not in spset]
            for i in range(1,self.n+1):
                if dist[i]==min(k) and i not in spset:
                    s=i
                    spset.append(s)
                    break
            for i in range(1, self.n+1):
                if self.roads[s][i]==1 and dist[s]+1<dist[i]:
                    dist[i]=dist[s]+1
                    prev[i]=s
                    if i==c:
                        path.append(c)
                        while c!=a:
                            path.append(prev[c])
                            c=prev[c]
                        return path
            k=[]
        return dist

乍一看，我有没有办法优化这个功能？我对python不是很有经验。一周前才开始。我只想让它快0.1到0.2秒。它是基于spt algo Dijkstra。我很抱歉没有那么生动

例如： 如果顶点（边）是：

(1,2)
(2,3)
(3,4)
(4,5)

dis(1,3)应该返回从1到3的路径，即[1,2,3]，否则，如果c为0，即dis(2,0)应该返回距离所有点2的距离，即[1,0,1,2,3]