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

重み付きグラフ

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