基本情報技術者アルゴリズムの問題をPythonでコーディングしてみた【平成29年春】

過去問コーディング。
今回の問題は、最短経路と最短距離の探索プログラムです。

過去問PDF「出典：平成29年度 春期 基本情報技術者試験 午後 問8」

プログラム

#配列Distanceを作成する(愚直に作ったけどもっといい方法ありそう)
Distance = [[0,2,8,4,-1,-1,-1],
            [2,0,-1,-1,3,-1,-1],
            [8,-1,0,-1,2,3,-1],
            [4,-1,-1,0,-1,8,-1],
            [-1,3,2,-1,0,-1,9],
            [-1,-1,3,8,-1,0,3],
            [-1,-1,-1,-1,9,3,0]]

def shortest_path(Distance,sp,dp):
    nPoint = len(Distance)

    #初期化
    sDist = float('inf') #出発地から目的地までの最短距離に初期値(∞)を格納する
    sRoute = [-1] * nPoint #最短経路上の地点の地点番号に初期値を格納する
    pRoute = [0] * nPoint #初期値格納（問題文にはなかったため追加)
    pDist = [float('inf')] * nPoint #出発地から各地点までの最短距離に初期値を格納する
    pFixed = [False] * nPoint #各地点の最短距離の確定状態に初期値を格納する

    pDist[sp] = 0 #出発地から出発地自体への最短距離に初期値を格納する

    while True:
        i = 0
        while i < nPoint: #未確定の地点を一つ探す
            if not(pFixed[i]):
                break #最内側の繰り返しから抜ける
            i = i + 1
        if i == nPoint: #出発地からすべての地点までの最短距離が確定
            break #していれば、最短経路探索処理を抜ける
        for j in range(i+1,nPoint): #最短距離がより短い地点を探す
            if not(pFixed[j]) and pDist[j] < pDist[i]:
                i = j

        sPoint = i
        print('sPoint='+ str(i))
        pFixed[sPoint] = True #出発地からの最短距離を確定する

        for j in range(0,nPoint):
            if Distance[sPoint][j] > 0 and not(pFixed[j]):
                newDist = pDist[sPoint] + Distance[sPoint][j]
                if newDist < pDist[j]:
                    pDist[j] = newDist
                    pRoute[j]  = sPoint
        print(pDist,pRoute)

    sDist = pDist[dp]
    j = 0
    i = dp
    
    while i != sp:
        sRoute[j] = i
        i = pRoute[i]
        j = j + 1

    sRoute[j] = sp

    print('最短経路の地点番号:'+str(sRoute))
    print('最短距離'+str(sDist))

shortest_path(Distance,0,6)

出力結果

sPoint=0
[0, 2, 8, 4, inf, inf, inf] [0, 0, 0, 0, 0, 0, 0]
sPoint=1
[0, 2, 8, 4, 5, inf, inf] [0, 0, 0, 0, 1, 0, 0]
sPoint=3
[0, 2, 8, 4, 5, 12, inf] [0, 0, 0, 0, 1, 3, 0]
sPoint=4
[0, 2, 7, 4, 5, 12, 14] [0, 0, 4, 0, 1, 3, 4]
sPoint=2
[0, 2, 7, 4, 5, 10, 14] [0, 0, 4, 0, 1, 2, 4]
sPoint=5
[0, 2, 7, 4, 5, 10, 13] [0, 0, 4, 0, 1, 2, 5]
sPoint=6
[0, 2, 7, 4, 5, 10, 13] [0, 0, 4, 0, 1, 2, 5]
最短経路の地点番号:[6, 5, 2, 4, 1, 0, -1]
最短距離13

↑設問解答用にいろいろ出力してます。

【過去問との主な相違点】
・配列Distanceを作成するためのコードを追加
・pRouteの初期化を追加
・「∞」はpythonではfloat('inf')

【感想】
ほぼ過去問のままでできました～

基本情報技術者試験の勉強も兼ねているこのコーディング。
今回は、問題文をそのままpythonのコードに直すだけでスラスラーと実行できてしまったので、
コード書いても、アルゴリズムの中身ちゃんと理解できませんでしたTT
やっぱり基本情報技術者のアルゴリズムって難しい～。

さて、
これからは忘れかけてる午前問題の勉強と、
午後問のコーディングと、
pythonの勉強を
その日の気分で勉強していこうと思います。

それではまた^^