35130


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

[ソースのあったサイトです](http://lethe2211.hatenablog.com/entry/2014/12/30/011030)  
バージョンはわかりませんでしたが2,3両方で動きました

下記がそのコードです。

[code]

    #! /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()
    
[/code]

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

[code]

    **********************************************************************
    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]
    
[/code]

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


CC BY-SA 3.0
2017-05-30T11:38:56.487
35129
2017-06-05T03:01:13.380
2017-06-05T03:01:13.380
2901
23462
question
python
pythonドックテストのエラーについて


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

[code]

    def foo(n):
        '''
        # のあとに受け取った数字を足して文字列にして印字
        >>> foo(3)
        #3
        '''
        print("#{}".format(n))
    
    
    if __name__ == "__main__":
        import doctest
        doctest.testmod()
    
[/code]

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


CC BY-SA 3.0
2017-05-30T12:12:59.657
35130
2017-05-30T12:12:59.657
2901
35129
answer