コードメモ > dijkstra


※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

#coding:utf-8
#幅優先探索とダイクストラ
#ダイクストラは特殊な場合の幅優先探索。

#まずは動かない疑似コードを書く。
def dijkstra(pool=[]):
  target_node = pool.popmin() #調べるべきノードの中から最小のを得る
  for next_node in target_node.next:
    next_node.cost = target_node.cost + next_node.own_cost #コストの更新を行う
    pool.append(next_node) #次回検索対象になる可能性があるので追加する

  return dijkstra(pool) #線形ループ

#これでは一生終わらないので、条件をくっつけます。
def dijkstra2(goal_node,pool=[]):
  target_node = popmin(pool) #調べるべきノードの中から最小のを得る
  if target_node == goal_node:
    return target_node #選び出した最小コストのノードがゴールノードなら終了。
  for link in target_node.next:
    if link.to.cost > target_node.cost + link.cost:
      link.to.cost = target_node.cost + link.cost #コストの更新を行う
      link.to.route = (target_node,) + target_node.route
    if not link.to in pool: 
      print 'append'
      pool.append(link.to)
  return dijkstra2(goal_node,pool) #線形ループ

'''
C言語では、「次回検索しなくてもいいノード」を記録する手法を用いていますが、
こっちの場合は「次回検索すべきノード」を記憶している点が違います。
実際後述した方が自然な考えかたなのではないでしょうか。
計算速度やメモリ効率,記述量はもちろん頭からは追いやってますが。
'''
def popmin(node_list):
  node_list.sort(lambda a,b:a.cost > b.cost)
  return node_list.pop()

class Node:
  def __init__(self,cost,next):
    self.cost = cost
    self.next = next
    self.route = ()

class Link:
  def __init__(self,cost,to):
    self.cost = cost
    self.to = to

def make_graph(matrix):
  graph = [Node(float('inf'),[]) for ln in matrix]
  for frm,line in enumerate(matrix):
    for to,cost in enumerate(line):
      if cost > 0:
        graph[frm].next.append(
          Link(cost,graph[to]))
        return graph

#こんな感じでどうでしょ。
def test_dijk():
  matrix=((0,1,0,0,1,0),
          (1,0,1,0,1,0),
          (0,1,0,1,0,0),
          (0,0,1,0,1,1),
          (1,1,0,1,0,0),
          (0,0,0,1,0,0))
  graph = make_graph(matrix)
  for node in graph:
    print node.next
  goalnode = dijkstra2(graph[0],[graph[5]])
  print 'cost:%d,route:%s'%(goalnode.cost,goalnode.route)

test_dijk()

*make_graphがうまく動いてくれない。時間切れになったので今度。マジでカスプログラマだぜ。