Dijkstra's Algorithm for finding the shortest route

[Glenton]

Hi All

Here is a very simple little class for finding a shortest route on a network, following Dijkstra's Algorithm:

#!/usr/bin/env python
#This is meant to solve a maze with Dijkstra's algorithm
from numpy import inf
from copy import copy
 
class Graph(object):
    """A graph object that has a set of singly connected,weighted,
    directed edges and a set of ordered pairs. Can be changed into
    a connection matrix. Vertices are [0,1,...,n], and edges are 
    [[1,2,3],[2,1,1],...] where the first means 1 connected to 2 
    with weight 3, and the second means 2 connected to 1 with 
    weight 1."""
 
    def __init__(self,vertices,edges):
        self.vertices=vertices
        self.size=len(self.vertices)
        self.edges=edges
        self.makematrix()
 
    def makematrix(self):
        "creates connection matrix"
        self.matrix=[]
        for i in range(self.size):
            self.matrix.append([])
            for j in range(self.size):
                self.matrix[i].append(inf)
        for edge in self.edges:
            self.matrix[edge[0]][edge[1]]=edge[2]
 
    def dijkstra(self,startvertex,endvertex):
        #set distances
        self.distance=[]
        self.route=[]
        for i in range(self.size):
            self.distance.append(inf)
            self.route.append([])
        self.distance[startvertex]=0
        self.route[startvertex]=[startvertex,]
        #set visited
        self.visited=[]
        self.current=startvertex
        while self.current<>None:
            self.checkunvisited()
            if endvertex in self.visited: break
        return self.distance[endvertex],self.route[endvertex]
 
    def checkunvisited(self):
        basedist=self.distance[self.current]
        self.visited.append(self.current)
        for vertex,dist in enumerate(self.matrix[self.current]):
            if vertex in self.visited: continue #only check unvisited
            #set the distance to the new distance
            if basedist+dist<self.distance[vertex]:
                self.distance[vertex]=basedist+dist
                self.route[vertex]=copy(self.route[self.current])
                self.route[vertex].append(vertex)
        #set next current node as one with smallest distance from initial
        self.current=None
        mindist=inf
        for vertex,dist in enumerate(self.distance):
            if vertex in self.visited: continue
            if dist<mindist:
                mindist=dist
                self.current=vertex
 
 
 
def main():
    #This solves the maze in the wikipedia article on Dijkstra's algorithm
    #Note that the vertices are numbered modulo 6, so 6 is called 0 here
    V=range(6)
    E=[[1,2,7],[1,3,9],[1,0,14],[2,1,7],[2,3,10],[2,4,15],[3,1,9],[3,2,10],
    [3,4,11],[3,0,2],[4,2,15],[4,3,11],[4,5,6],[5,4,6],[5,0,9],[0,1,14],
    [0,3,2],[0,5,9]]
    m=Graph(V,E)
    print "size of graph is", m.size
 
    print "distance and best route is", m.dijkstra(1,5)
 
 
 
if __name__=="__main__": main()
 

The main here is just an example, implementing the network shown in the wikipedia article. To use it, you simply need to get your network arranged into a list of vertices (0,1,...,n-1), and your edges into a list of coordinates of the form [a,b,d], where the edge is from a to b with weight d. If you want undirected, you simply need to add [b,a,d]. If you want unweighted you need to just set d=1.

I've been planning the design of some mazes for the local science centre, which is why I've got this! Any improvements/comments are welcome.

[Glenton]

Hi

So here I've beefed up the Graph class a little bit.
- The main addition is the implementation of Kruskal's algorithm for finding minimum spanning trees. The neat part is that it uses Dijkstra's algorithm to determine whether two points are connected (at least I found it neat).
- Other improvements are the ability to add vertices and edges to a graph on the fly, and to input a graph by its matrix, rather than by its vertices and edges sets.

#!/usr/bin/env python
#This is meant to solve a maze with Dijkstra's algorithm
from numpy import inf
from copy import copy
from bisect import bisect_left
 
class Graph(object):
    """A graph object that has a set of singly connected,weighted,
    directed edges and a set of ordered pairs. Can be changed into
    a connection matrix. Vertices are [0,1,...,n], and edges are 
    [[1,2,3],[2,1,1],...] where the first means 1 connected to 2 
    with weight 3, and the second means 2 connected to 1 with 
    weight 1."""
 
    def __init__(self,vertices=[],edges=[]):
        self.vertices=vertices
        self.order=len(self.vertices)
        self.edges=edges
        self.size=len(edges)
        self.makematrix()
 
    def addvertice(self,vertice):
        self.vertices.append(vertice)
        self.order=len(self.vertices)
        self.makematrix()
 
    def addvertices(self,vertices):
        self.vertices+=vertices
        self.order=len(self.vertices)
        self.makematrix()
    def addedge(self,edge):
        self.edges.append(edge)
        self.size=len(self.edges)
        self.makematrix()
 
    def addedges(self,edges):
        self.edges+=edges
        self.size=len(self.edges)
        self.makematrix()
 
    def orderedges(self):
        E=[]
        eo=[]
        for e in self.edges:
            n=bisect_left(eo,e[2])
            eo.insert(n,e[2])
            E.insert(n,e)
        self.edges=E
    def makematrix(self):
        "creates connection matrix"
        self.matrix=[]
        for i in range(self.order):
            self.matrix.append([])
            for j in range(self.order):
                self.matrix[i].append(inf)
        for edge in self.edges:
            self.matrix[edge[0]][edge[1]]=edge[2]
 
    def dijkstra(self,startvertex,endvertex):
        #set distances
        self.distance=[]
        self.route=[]
        for i in range(self.order):
            self.distance.append(inf)
            self.route.append([])
        self.distance[startvertex]=0
        self.route[startvertex]=[startvertex,]
        #set visited
        self.visited=[]
        self.current=startvertex
        while self.current<>None:
            self.checkunvisited()
            if endvertex in self.visited: break
        return self.distance[endvertex],self.route[endvertex]
 
    def checkunvisited(self):
        basedist=self.distance[self.current]
        self.visited.append(self.current)
        for vertex,dist in enumerate(self.matrix[self.current]):
            if vertex in self.visited: continue #only check unvisited
            #set the distance to the new distance
            if basedist+dist<self.distance[vertex]:
                self.distance[vertex]=basedist+dist
                self.route[vertex]=copy(self.route[self.current])
                self.route[vertex].append(vertex)
        #set next current node as one with smallest distance from initial
        self.current=None
        mindist=inf
        for vertex,dist in enumerate(self.distance):
            if vertex in self.visited: continue
            if dist<mindist:
                mindist=dist
                self.current=vertex
 
 
    def kruskal(self):
        self.orderedges()
        E=self.edges
        T=Graph(self.vertices,[])
        for e in E:
            if T.dijkstra(e[0],e[1])[0]==inf:
                T.addedge(e)
                T.addedge([e[1],e[0],e[2]])
            if T.order-1==T.size/2:break
        return T
    def weight(self):
        return sum([e[2] for e in self.edges])
    def setmatrix(self,matrix):
        E=[]
        V=range(len(matrix))
        for i,row in enumerate(matrix):
            for j,col in enumerate(row):
                if col<inf:
                    E.append([i,j,col])
        self.__init__(V,E)
 
def main():
    #This solves the maze in the wikipedia article on Dijkstra's algorithm
    #Note that the vertices are numbered modulo 6, so 6 is called 0 here
    V=range(6)
    E=[[1,2,7],[1,3,9],[1,0,14],[2,1,7],[2,3,10],[2,4,15],[3,1,9],[3,2,10],
    [3,4,11],[3,0,2],[4,2,15],[4,3,11],[5,4,6],[5,0,9],[0,1,14],
    [0,3,2],[0,5,9],[4,5,6]]
    m=Graph(V,E)
    print "order of graph is", m.order
    print "distance and best route is", m.dijkstra(1,5)
    print "edges", m.edges
    m.orderedges()
    print "ordered edges", m.edges
    T=m.kruskal()
    print "Minimum spanning tree:"
    print "Vertices",T.vertices
    print "Edges",T.edges
    print "Matrix:"
    print T.matrix
    print "Weight",T.weight()/2
    M=m.matrix
    m2=Graph()
    m2.setmatrix(M)
 
    M=[[inf,16,12,21,inf,inf,inf],
        [16,inf,inf,17,20,inf,inf],
        [12,inf,inf,28,inf,31,inf],
        [21,17,28,inf,18,19,23],
        [inf,20,inf,18,inf,inf,11],
        [inf,inf,31,19,inf,inf,27],
        [inf,inf,inf,23,11,27,inf]]
    G=Graph()
    G.setmatrix(M)
    T=G.kruskal()
    print "Savings is",G.weight()/2-T.weight()/2
 
if __name__=="__main__": main()