python: Depth-First Search (7)

Abstract: the shortest distance from City A to B

The result:
start point:  A
end point:  F
The shortest way: ['A', 'F']
The distance of the way: 10.0



 
 The script:
# -*- coding: utf-8 -*-
"""
Created on Tue Jul  7 22:35:53 2015

@author: yuan
"""
import numpy as np
import pandas as pd

#the shortest distance from A to B
class network_pd:
    def __init__(self, connects):
        self.connects=np.array(connects)
        self.edges_num=len(self.connects)
        self.nodes=np.unique(np.array(self.connects)[:,:2])
        self.nodes_num=len(self.nodes)
  
    def read_direction_connects(self):
        net=np.zeros((self.nodes_num,self.nodes_num))
        net=pd.DataFrame(net, columns=self.nodes, index=self.nodes)
        #get 2-D marix to store network
        for row in range(self.edges_num):
            nodeA=self.connects[row][0]
            nodeB=self.connects[row][1]
            #print nodeA, nodeB          
            net[nodeA][nodeB]=self.connects[row][2]
            net[nodeA][nodeA]=-1#remove self-connection
            net[nodeB][nodeB]=-1
        #print net
        return net
#
class best_way:
    def __init__(self, net,start_point, end_point):
        self.net=pd.DataFrame(net)
        self.nodes=list(self.net.columns)
        self.nodes_num=len(self.net.columns)
        self.out=[]
        self.start_point=start_point
        self.end_point=end_point
        self.min=99999
        print self.net
  
    def DFS(self, a_node, points, dist):
      
        if dist> self.min:
            return
        if a_node==self.end_point:
            if dist<self.min:
                self.min=dist
                self.out=list(points)
                print self.min, self.out
            return
            
        for b_node in self.nodes:
            if(self.net[a_node][b_node]>0 and b_node not in points):
                #print a_node, b_node, dist, points
                points.append(b_node)
                #recursion
                self.DFS(b_node, points, dist+self.net[a_node][b_node])
                points.remove(b_node)
        return
      
    def shortest_distance(self):
        points=[self.start_point]
        dist=0
        #recursive functions
        self.DFS(self.start_point, points, dist)
        print "start point: ", self.start_point
        print "end point: ", self.end_point
        print 'The shortest way:', self.out
        print 'The distance of the way:', self.min



#store network into dat frame using panda
connects=[['A','B',2],['B','C',3],['A','C',6],['C','A',6],['A','E',3],
          ['E','C',4], ['C','D', 4], ['D','F',5], ['A','F',10] ]
net=network_pd(connects)
nets=net.read_direction_connects()

#
start_point='A'
end_point='F'
dist=best_way(nets,start_point, end_point)
dist.shortest_distance()