1

pythonをやってみようと思い環境が正常動作するか試しにネットにあったソースを動かしてみました。
環境: windows10 64bit
python 2.7,3.6

ソースのあったサイトです
バージョンはわかりませんでしたが2,3両方で動きました

下記がそのコードです。

#! /usr/bin/env python
# -*- coding: utf-8 -*-

import heapq

class Dijkstra(object):
    def dijkstra(self, adj, start, goal=None):
        '''
        ダイクストラアルゴリズムによる最短経路を求めるメソッド
        入力
        adj: adj[i][j]の値が頂点iから頂点jまでの距離(頂点iから頂点jに枝がない場合,値はfloat('inf'))となるような2次元リスト(正方行列)
        start: 始点のID
        goal: オプション引数.終点のID
        出力
        goalを引数に持つ場合,startからgoalまでの最短経路を格納したリストを返す
        持たない場合は,startから各頂点までの最短距離を格納したリストを返す
        >>> d = Dijkstra()
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
        [0, 2, 4, 5, 8] # 例えば,始点0から頂点3までの最短距離は5となる
        >>> d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
        [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
        '''
        num = len(adj)          # グラフのノード数
        dist = [float('inf') for i in range(num)] # 始点から各頂点までの最短距離を格納する
        prev = [float('inf') for i in range(num)] # 最短経路における,その頂点の前の頂点のIDを格納する

        dist[start] = 0
        q = []                  # プライオリティキュー.各要素は,(startからある頂点vまでの仮の距離, 頂点vのID)からなるタプル
        heapq.heappush(q, (0, start)) # 始点をpush

        while len(q) != 0:
            prov_cost, src = heapq.heappop(q) # pop

            # プライオリティキューに格納されている最短距離が,現在計算できている最短距離より大きければ,distの更新をする必要はない
            if dist[src] < prov_cost:
                continue

            # 他の頂点の探索
            for dest in range(num):
                cost = adj[src][dest]
                if cost != float('inf') and dist[dest] > dist[src] + cost:
                    dist[dest] = dist[src] + cost # distの更新
                    heapq.heappush(q, (dist[dest], dest)) # キューに新たな仮の距離の情報をpush
                    prev[dest] = src                      # 前の頂点を記録

        if goal is not None:
            return self.get_path(goal, prev)
        else:
            return dist

    def get_path(self, goal, prev):
        '''
        始点startから終点goalまでの最短経路を求める
        '''
        path = [goal]           # 最短経路
        dest = goal

        # 終点から最短経路を逆順に辿る
        while prev[dest] != float('inf'):
            path.append(prev[dest])
            dest = prev[dest]

        # 経路をreverseして出力
        return list(reversed(path))

if __name__ == '__main__':
    import doctest
    doctest.testmod()

結果は以下のようになりました。

**********************************************************************
File "test.py", line 17, in __main__.Dijkstra.dijkstra
Failed example:
    d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0)
Expected:
    [0, 2, 4, 5, 8] # 例えば,始点0から頂点3までの最短距離は5となる
Got:
    [0, 2, 4, 5, 8]
**********************************************************************
File "test.py", line 19, in __main__.Dijkstra.dijkstra
Failed example:
    d.dijkstra([[float('inf'), 2, 4, float('inf'), float('inf')], [2, float('inf'), 3, 5, float('inf')], [4, 3, float('inf'), 1, 4], [float('inf'), 5, 1, float('inf'), 3], [float('inf'), float('inf'), 4, 3, float('inf')]], 0, goal=4)
Expected:
    [0, 2, 4] # 頂点0から頂点4までの最短経路は0 -> 2 -> 4となる
Got:
    [0, 2, 4]
**********************************************************************
1 items had failures:
   2 of   3 in __main__.Dijkstra.dijkstra
***Test Failed*** 2 failures.
*************************************************************


Expected:
[0, 2, 4, 5, 8] # 例えば,始点0から頂点3までの最短距離は5となる
Got:
[0, 2, 4, 5, 8]

をみると
expectedgotの値は一致しているように見えます。
しかしこれはfailed exampleとなっています。
これは一体なぜなのでしょうか。
virtual boxで linux mintを使ってみても同じ結果でした。
解決法をよろしくお願いします。

1 件の回答 1

2

Doctest の返り値のところにコメントは書けない(文字通りに解釈される)からです.

def foo(n):
    '''
    # のあとに受け取った数字を足して文字列にして印字
    >>> foo(3)
    #3
    '''
    print("#{}".format(n))


if __name__ == "__main__":
    import doctest
    doctest.testmod()

問題の例では [0, 2, 4, 5, 8] # 例えば,始点0から頂点3までの最短距離は5となる という # 以降も無視されずに比較の対象になり,期待された値が返ってきていない,と報告されています.

1
  • コメントを削除してみたら動きました。
    – noname
    2017年5月31日 5:08

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。