sasaharayuugo.net

06年度トライアル問題　問題1

『図の各数字は2つの○の間を移動するとっきの所要時間（単位：分）を示しています。AからBまで移動するときにかかる最も短い時間を求めなさい。

○	4	○	5	○	8	B
6		9		3		7
○	5	○	4	○	6	○
4		6		5		5
○	4	○	9	○	6	○
5		8		7		9
A	4	○	7	○	8	○

』　

#[隣接する節点の番号, 移動のコスト]
    graph = [
        [[1, 4], [4, 6]],
        [[0, 4], [2, 5], [5, 9]],
        [[1, 5], [3, 8], [6, 3]],
        [[2, 8], [7, 7]],
        [[0, 6], [5, 5], [8, 4]],
        [[1, 9], [4, 5], [6, 4], [9, 6]],
        [[2, 3], [5, 4], [7, 6], [10, 5]],
        [[3, 7], [6, 6], [11, 5]],
        [[4, 4], [9, 4], [12, 5]],
        [[5, 6], [8, 4], [10, 9], [13, 8]],
        [[6, 5], [9, 9], [11, 6], [14, 7]],
        [[7, 5], [10, 6], [15, 9]],
        [[8, 5], [13, 4]],
        [[9, 8], [12, 4], [14, 7]],
        [[10, 7], [13, 7], [15, 8]],
        [[11, 9], [14, 8]]
    ]

    #PQは本当はPriority Queue、つまり優先度キューだったが、今回は実装で怠けるためにリストにしたので、決して実際に使ってはいけない
    def singleSourceShortest(graph, start, goal):
        vertex_amount = len(graph)
        dist = [float("inf")] * vertex_amount   #その節点に行くまでのコスト
        pred = [-1] * vertex_amount   #どこから来たか
        PQ = []   #優先度リスト　探索する際にその時のdist[v]を節点の優先度として使う

        dist[start] = 0
        for v_index in range(vertex_amount):
            PQ.append((v_index, dist[v_index]))
        PQ.sort(key=lambda x: x[1], reverse=True)   #こう書くらしい（公式ドキュメントの「ソート HOW TO」曰く）


        while(PQ != []):
            u_tuple = PQ.pop()
            u_index = u_tuple[0]
            u = graph[u_index]

            for v in u:
                v_index = v[0]
                w = v[1]
                newLen = dist[u_index] + w
                if newLen < dist[v_index]:
                    dist[v_index] = newLen
                    pred[v_index] = u_index
                    PQ = [i for i in PQ if i[0] != v_index]
                    PQ.append((v_index, dist[v_index]))
            PQ.sort(key=lambda x: x[1], reverse=True)

        now_v = goal
        print("goal")
        while(pred[now_v] != -1):
            print("↑")
            now_v = pred[now_v]
            print(now_v)


    singleSourceShortest(graph, 12, 3)
    

$ python3 ダイクストラ.py
    goal
    ↑
    2
    ↑
    6
    ↑
    5
    ↑
    4
    ↑
    8
    ↑
    12

　

12年度トライアル問題　問題8

『次の立体を頂点Aからスタートして返上を通ってAにもどってくるような方法は、全部で何通りありますか。ただし、同じ辺を2度通ってはいけません。

（図は省略　ABCDの三角錐）』
　

#pythonでは無い

    graph := [
        "A" : ["B", "C", "D"],
        "B" : ["A", "C", "D"],
        "C" : ["A", "B", "D"],
        "D" : ["A", "B", "C"]
    ];   #辞書、()にするか[]にするか迷うな

    def visit_v(graph, current_v, start) {
        or(next_v in graph[current_v]) {   #orにおいて、データを共有するかどうかという設定項目が必要か
            graph[current_v].remove(next_v);
            graph[next_v].remove(current_v);

            current_v := next_v;

            if(current_v != start) {   # || graph[current_v] != []　を入れるべきか
                current_v := visit_v(graph, current_v, start);
            }
        }

        return current_v;
    }

    start := "A";
    current_v := "A";

    current_v := visit_v(graph, current_v, start);

    current_v == "A";

    print(数);

こんな感じだろうか。
return文が必要だと気付いて付け足した。これで大丈夫かな。しかしやっぱりpythonは良かったなあ。