DEV

Python3 - アルゴリズム（重み付きグラフ・最短経路探索・ダイクストラのアルゴリズム）

#Python#アルゴリズム#グラフ

参考：欲張り法 (greedy strategy)

重み付きグラフ

networkxでつくった重みグラフ

networkxのコードサンプル

上記は重み付きのグラフです。これはnetworkxで書きました。コードは下記です。

import numpy as np
import matplotlib.pyplot as plt
import networkx as nx
g = [
    [ 0, 10,  0, 20,  0,  0,  0, 30],   # A (0)
    [10,  0, 10,  0,  0,  0,  0,  0],   # B (1)
    [ 0, 10,  0,  0, 20,  0,  0,  0],   # C (2)
    [20,  0,  0,  0,  0, 20,  0,  0],   # D (3)
    [ 0,  0, 20,  0,  0,  0,  0, 20],   # E (4)
    [ 0,  0,  0, 20,  0,  0, 10,  0],   # F (5)
    [ 0,  0,  0,  0,  0, 10,  0, 10],   # G (6)
    [30,  0,  0,  0, 20,  0, 10,  0]    # H (7)
]
nodes = np.array(['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h'])
edges = []
edge_labels = {}
for hi, hv  in enumerate(g):
    for wi, wv in enumerate(hv):
        if(wv):
            tpl = (nodes[hi], nodes[wi])
            edges.append(tpl)
            edge_labels[tpl] = wv
G = nx.Graph()
G.add_nodes_from(nodes)
G.add_edges_from(edges)
pos = nx.spring_layout(G)
nx.draw_networkx(G, pos, with_labels=True)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)
plt.axis("off")
plt.show()

この重み付きグラフは参考サイトにのってるやつです。参考サイトのダイクストラのアルゴリズムをやってみます。

ダイクストラのアルゴリズム

重み付きグラフの最短経路探索のアルゴリズムの一つです。効率は結構いいですが、各地点のコストに負の値があると使えません。

コードサンプル

def print_path(prev, cost):
    for i in range(len(prev)):
        print("%d, prev = %d, cost = %d" %  (i, prev[i], cost[i]))


def get_path(start, goal, prev):
    path = []
    now = goal
    path.append(now)
    while True:
        path.append(prev[now])
        if prev[now] == start: break
        now = prev[now]
    path.reverse()
    return path


def search(glaph, start, goal):
    MAX_VAL = 0x10000000
    g_size = len(glaph)
    visited = [False] * g_size
    cost = [MAX_VAL] * g_size
    prev = [None] * g_size
    cost[start] = 0
    prev[start] = start
    now = start
    while True:
        min = MAX_VAL
        next = -1
        visited[now] = True
        for i in range(g_size):
            if visited[i]: continue
            if glaph[now][i]:
                tmp_cost = glaph[now][i] + cost[now]
                if cost[i] > tmp_cost:
                    cost[i] = tmp_cost
                    prev[i] = now
            if min > cost[i]:
                min = cost[i]
                next = i
        if next == -1: break
        now = next
    print_path(prev, cost)
    return [get_path(start, goal, prev), cost[goal]]


g = [
    [ 0, 10,  0, 20,  0,  0,  0, 30],   # A (0)
    [10,  0, 10,  0,  0,  0,  0,  0],   # B (1)
    [ 0, 10,  0,  0, 20,  0,  0,  0],   # C (2)
    [20,  0,  0,  0,  0, 20,  0,  0],   # D (3)
    [ 0,  0, 20,  0,  0,  0,  0, 20],   # E (4)
    [ 0,  0,  0, 20,  0,  0, 10,  0],   # F (5)
    [ 0,  0,  0,  0,  0, 10,  0, 10],   # G (6)
    [30,  0,  0,  0, 20,  0, 10,  0]    # H (7)
]


path, cost = search(g, 5, 1)
print(path, 'cost: ', cost)

結果

0, prev = 3, cost = 40
1, prev = 0, cost = 50
2, prev = 4, cost = 60
3, prev = 5, cost = 20
4, prev = 7, cost = 40
5, prev = 5, cost = 0
6, prev = 5, cost = 10
7, prev = 6, cost = 20
[5, 3, 0, 1] cost:  50

上記はfからbまでの最短経路を探しております。どういう動きなのかを言葉で書くのが難しい。。

アルゴリズムの仕組み

最初にする主なこと

  • スタート地点のコストを0にする。
  • 現在地をスタート地点にする。

ループでしている主なこと

  • 現在地を訪問済み（チェック済み）にする。
  • 現在地から訪問可能な地点の、各コスト（現在地までのコスト＋現在地から訪問可能地点までのコスト）を出して、今まで記憶しているコストより低ければ更新する。
  • 訪問済みでない地点の記憶されているコストで最も低いコストの地点を現在地にする。
  • 以降、上記３つを繰り返す。
  • 訪問済みの地点がなくなったらループを終了させる。

ループ終了後どうなっているか？

  • スタート地点からの各地点までの最短コストと、パスを記憶している。上記コードの場合、cost配列にコストが入っていて、prev配列に各地点の直前の地点が入っている。

注意点

  • 各地点のコストがマイナスのものがあるとこのアルゴリズムは使えない。

改善点

  • ヒープを使うとより効率的になるらしいので、次にヒープを使ってつくってみる。
  • 最短経路をnetworkxで表示させるようにしたい。