最短経路探索（ダイクストラ法）

// RunOver: Detail
// input0: Polyline Graph
// input1: Polyline

vector start = point(1, "P", 0);
vector goal = point(1, "P", 1);

// 始点
vector cross;
vector uv;
vector origin = start + set(0, 1, 0) * 50000;
vector dir = set(0, -1, 0) * 100000;
int hitId = intersect(1, origin, dir, cross, uv);
if(hitId >= 0)
    i@startId = nearpoint(0, cross);
else
    i@startId = nearpoint(0, start);

// 終点
origin = goal + set(0, 1, 0) * 50000;
dir = set(0, -1, 0) * 100000;
hitId = intersect(1, origin, dir, cross, uv);
if(hitId >= 0)
    i@goalId = nearpoint(0, cross);
else
    i@goalId = nearpoint(0, goal);

// RunOver: Points

// 隣り合うポイント
int neighbours[] = neighbours(0, @ptnum);
i[]@connectedPoint = neighbours;

// 隣り合うポリライン
int connectedPrim[] = pointprims(0, @ptnum);
i[]@connectedPrim = connectedPrim;

// ポリラインの長さ
f[]@distance;
for(int i = 0; i < len(neighbours); i++)
{
    vector pos = point(0, "P", neighbours[i]);
    f[]@distance[i] = length(pos - @P);
}

#
# ダイクストラの経路探索
#

node = hou.pwd()
geo = node.geometry()

from collections import deque
import time

# Start
start_time = time.time()

# 地点クラス
class Node:
    def __init__(self, connect, dist):
        # 直前のインデックス
        self.prevPt = -1
        # フラグ
        self.flag = 0
        # コスト（一応大きな数を入れておく）
        self.totalCost = 100000.0
        # 接続する道路
        self.connect = connect
        # 道路の距離
        self.dist = dist

start = geo.intAttribValue('startId')
goal = geo.intAttribValue('goalId')

# ルートリスト
routeList = deque([])

# ポイント総数
nPoints = len(geo.points())

# 分岐するルートと距離の情報を格納する
connect = []
dist = []

for pt in geo.points():
    connect.append(pt.intListAttribValue("connectedPoint"))
    dist.append(pt.floatListAttribValue("distance"))
    
# ノードクラスのリストを初期化
node = []
for i in range(nPoints):
    node.append(Node(connect[i], dist[i]))    
   
#
# 計算開始
#

# startからのルートをリストに入れる
node[start].flag = 1
node[start].prevPt = start
node[start].totalCost = 0.0

routeList.append(start)

# 処理
count = 0
while len(routeList) > 0:
    # リストから引き出す
    currentPt = routeList.popleft()

    for i in range(len(node[currentPt].connect)):
        nextPt = node[currentPt].connect[i]
        cost = node[currentPt].totalCost + node[currentPt].dist[i]

        # すでに探索済みのポイント
        if node[nextPt].flag == 1:
            if cost < node[nextPt].totalCost:
                node[nextPt].totalCost = cost
                node[nextPt].prevPt = currentPt
                routeList.append(nextPt)
        # 新規に探索するポイント
        else:
            node[nextPt].totalCost = cost
            node[nextPt].prevPt = currentPt
        
            # 探索済みフラグを立てる
            node[nextPt].flag = 1
            
            # ゴールの地点なら次の地点は探索しない
            if nextPt != goal:
                routeList.append(nextPt)
                
        count = count + 1
                
# ルートを検索
if node[goal].prevPt != -1:
    route = []
    
    pt = goal
    while(pt != start):
        route.append(pt)
        pt = node[pt].prevPt
        
    route.append(start)
    route.reverse()
    
    # Detailに保存
    geo.addArrayAttrib(hou.attribType.Global, 'route', hou.attribData.Int, 1)
    geo.setGlobalAttribValue('route', route)
    
    geo.addAttrib(hou.attribType.Global, 'dist', 0.0)
    geo.setGlobalAttribValue('dist', node[goal].totalCost)
    
    geo.addAttrib(hou.attribType.Global, 'start', 0)
    geo.setGlobalAttribValue('start', start)
    
    geo.addAttrib(hou.attribType.Global, 'goal', 0)
    geo.setGlobalAttribValue('goal', goal)
    
    #print route
    print (node[goal].totalCost)
    print ("num search:" + str(count))
    
    # End
    elapsed_time = time.time() - start_time
    print ("dykstra_route::time:{0}".format(elapsed_time) + "[sec]")

// RunOver: Detail
// input0: None
// input1: Python SOP

int route[] = detail(1, "route", 0);

int prim = addprim(0, "polyline");

for(int i = 0; i < len(route); i++)
{
    vector pos = point(1, "P", route[i]);
    int pt = addpoint(0, pos);
    addvertex(0, prim, pt);
}