从BFS到Dijkstra

本文内容基本上出自： Grokking.Algorithms.An.illustrated.guide.for.programmers.and.other.curious.people

BFS：解决什么问题？
1. Is there a path from node A to node B?
2. What is the shortest path from node A to node B?
适用于无权重的图，以前的帖子里面的wordladder问题，也是BFS的应用。
wordladder: http://blog.chinaunix.net/uid-7713641-id-5695587.html

下面的例子从“you"开始寻找第一个字符串结束是"m"的字符串，将每个节点的out edge 放入双端队列，然后最左端的出队，依次处理每个element, 是则打印，否则加入一个
叫searched的列表，以后不再来查询同样的element.  

graph={"you":["alice","bob","claire"],"bob":["anuj","peggy"],"alice":["peggy"],"claire":["thom","jonny"],"anuj":["thom","jonny"],"peggy":[],"thom":[],"jonny":[]}

from collections import deque

def bfs(name):
    search_queue=deque()
    #search_queue+=graph["you"]
    search_queue.extend(graph[name])
    searched=[]
    while search_queue: #while the queue is not empty
        person=search_queue.popleft() #left out
        if not person in searched:
            if person_is_seller(person):
                print("{} is a mango seller".format(person))
                return True
            else:
                #search_queue+=graph[person]
                search_queue.extend(graph[person])
                searched.append(person)         #mark as searched
    return False

def person_is_seller(name):
    #return name.startswith("m")
    return name[-1]=='m'

bfs("you")

2. Dijkstra 算法解决什么问题：   
What is the shortest path from node A to node B in a weighted graph（DAG),仅仅适用于有向无环图。

代码在这里：
从"start" 到"fin" 最短的路径是什么

graph={"start":{"a":6,"b":2},"a":{"fin":1},"b":{"a":3,"fin":5},"fin":{}}

infinity=float("inf")

costs={}
costs["a"]=6
costs["b"]=2
costs["fin"]=infinity

parents={}
parents["a"]="start"
parents["b"]="start"
parents["fin"]=None

processed=[]

def find_lowest_cost_node(costs):
    lowest_cost=float("inf")
    lowest_cost_node=None
    for node in costs: #go throught each node
        cost=costs[node]
        if cost < lowest_cost and node not in processed: #if it's lowest cost so far and has not been processed yet
            lowest_cost=cost        #set it as the new lowest-cost node
            lowest_cost_node=node
    return lowest_cost_node

node=find_lowest_cost_node(costs)           #find the lowest-cost node that you have not processed yet
while node is not None:         #if you have processed all the nodes,this while loop is done
    cost=costs[node]
    neighbors=graph[node]
    for n in neighbors.keys():              #go throught all the neighbors of this node
        new_cost=cost+neighbors[n]         #if it's cheaper to get to this neightbor
        if costs[n] > new_cost: #by going through this node
            costs[n]=new_cost               #update cost for this node
            parents[n]=node                 #this node become the new parent for this neighbor
    processed.append(node) #mark the node as procesed
    node=find_lowest_cost_node(costs)


print(costs)

3. Dijkstra只有在权重为正数的时候才适用，如果权重有负数，则应该使用Bellman-Ford algorithm