---
title: 20260929_MicrosoftDataAnalyticsDay_最短経路と最長経路，そしてオントロジーへ－Fabric Appsで作る「日本全国 駅間経路探索」と意味の世界への応用－
tags: 
author: [Masahide TAKASUKA](https://image.docswell.com/user/3324212129)
site: [Docswell](https://www.docswell.com/)
thumbnail: https://bcdn.docswell.com/page/47ZLN8P9J3.jpg?width=480
description: 2026/9/29(火) 19:00 〜 21:00 開催  Microsoft Data Analytics Day(Online) 勉強会 2026/09 https://sqlserver.connpass.com/event/406761/
published: September 27, 26
canonical: https://image.docswell.com/s/3324212129/Z4NWVQ-2026-09-27-190836
---
# Page. 1

![Page Image](https://bcdn.docswell.com/page/47ZLN8P9J3.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
最短経路と最長経路，
そしてオントロジーへ
Fabric Appsで作る「日本全国 駅間経路探索」と意味の世界への応用
2026/9/29
高須賀 将秀


# Page. 2

![Page Image](https://bcdn.docswell.com/page/YJ6W8PMDJV.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
2 /26
自己紹介
たかすか
まさひで
高須賀 将秀
博士（情報学）（2023/3）
研究分野：組合せ最適化，数理最適化，オペレーションズ・リサーチ（OR），グラフ理論
高須賀将秀のホームページ
所属：NTT西日本 デジタル改革推進部（2021/8～），
法政大学 デザイン工学部 兼任講師（2024/4～），個人事業（Udemy講師等）（2024/6～）
業務：データドリブン経営を牽引する立場
・データ活用基盤のシステム開発 ・データ分析手法の研究
・データ分析活用事例の提案 ・デジタル人材育成
New!
資格：クラウド資格（AWS全冠，Azure/AppliedSkills全冠，GCP全冠， Snowflake全冠），
受賞：AWS Top Engineers（’26） ，AWS Community Builders（’26），AWS All Certifications Engineers（’24/’25/’26），
Microsoft Top Partner Engineer Award（’24, ‘26），Microsoft Innovative Educator Experts 2025-2026，
Google Cloud Partner Top Engineer（’26），Google Cloud Partner All Certification Holders（‘25），
Jagu‘e’r Award 優秀賞（’25），Snowflake Squad（’24, ‘25）， Microsoft Certified Trainer（MCT）


# Page. 3

![Page Image](https://bcdn.docswell.com/page/GJ5M9KZ8J4.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
3 /26
本日お話しすること
1
原点
3年前に設定したテーマ「データトリガーのユースケース発掘」
2
理論
最短経路と最長経路は似て非なる2つの最適化問題
3
実装
Fabric Apps で作る 日本全国駅間経路探索アプリ
4
展望
グラフアルゴリズムでオントロジーの質を高める


# Page. 4

![Page Image](https://bcdn.docswell.com/page/9E292WRV7R.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
4 /26
3年前に設定したテーマ：データ活用のユースケース発掘の自律化
2023年当時の資料．課題起点ではなく，データ構造の抽出からユースケースそのものを発掘する構想．
MSIISM2023の発表抜粋


# Page. 5

![Page Image](https://bcdn.docswell.com/page/D7Y4YLDQEM.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
5 /26
課題起点の分析からデータ起点の発掘へ
現状：課題起点のデータ分析
目指した姿：データ起点の発掘
■ 実業務で見えている課題から出発し，必要なデータ
■ 基盤上の全データからデータ構造を抽出する
を集めて分析する
■ 構造の中から潜在的・複合的なユースケースを機械
■ 見えている課題しか扱えず，活用シーンが限定される
が提案する
■ 基盤に眠る大量のデータが活かされない
■ 分析のハードルを下げ，施策横断的なデータ活用を
推進する
当時の壁は，機械が「業務コンテキスト」を持てなかったこと．データの意味構造は人手で抽出するしかなかった．


# Page. 6

![Page Image](https://bcdn.docswell.com/page/VENYP462J8.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
6 /26
この2ヶ月の発表の系譜
2026.07
2026.08
2026.09
データの共有から
コンテキストの共有へ
セマンティックモデルと
オントロジーの自動生成
グラフアルゴリズムで
オントロジーの質を高める
Fabric × Snowflake．単一コピーの
Icebergで両プラットフォームをつなぎ，データだ
けでなくカタログやエージェントを共有する話
業務概念(Entity・Relationship)の層を，人
手ではなく自動で立ち上げる話
本日．生成されたオントロジーを「測り，鍛える」
ための数理最適化の視点
セマンティックモデルやオントロジー技術の発展で，業務コンテキストをある程度自動生成できる時代が来た．3年前の思想が実現する日は着
々と近づいている．


# Page. 7

![Page Image](https://bcdn.docswell.com/page/Y79P3QLDE3.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
7 /26
意味層のスタックが揃ってきた
Data Agent
オントロジーとセマンティックモデルを参照し，自然言語で回答する
ここでのポイント
■ オントロジーは実質，知識グラフとして
扱われる
Fabric IQ
組織で共有するビジネスコンテキスト層
■ AIの回答品質は，この意味層の「質」
に強く依存する
オントロジー
Entity Type・Property・Relationship による業務概念のグラフ
＝ 知識グラフ
セマンティックモデル
テーブル・メジャー・リレーションの意味付け
→ 本日のポイントは，数理最適化問題の「最長経路問題」
■ では、その質はどう測り，どう高めるの
か？


# Page. 8

![Page Image](https://bcdn.docswell.com/page/G78DMGX57D.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
8 /26
今回の題材：日本全国駅間経路探索アプリ
■ 実際の鉄道網(ekidata.jp)を題材に，任意の2駅間の経路を計算す
るWebアプリをMicrosoft Fabric Appsで実装
■ 最短経路(ダイクストラ法)と最長経路(単純経路・営業キロ最大)を同
時に計算し，地図上に色分け表示
■ 計算結果はFabric Lakehouse / SQL Databaseに保存
10,465
9,920
1,699
駅(営業中)
路線内区間
乗り換え辺
データ出典：駅データ.jp (ekidata.jp)．営業中の駅のみ抽出．


# Page. 9

![Page Image](https://bcdn.docswell.com/page/L7LM3G83JR.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
9 /26
最短経路問題と最長路問題の違い
最短経路
最長経路(近似解)
4ホップ / 3.2 km
498ホップ / 1290.2 km
江古田 → 桜台 → 練馬 → 新江古田
関東平野から信越・東北を一周して戻る
起点と終点は徒歩10分の隣駅(江古田と新江古田)．距離の差は約400倍．ただし本当に違うのは計算の難しさ


# Page. 10

![Page Image](https://bcdn.docswell.com/page/4EMYDQ6MEW.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
10 /26
最短経路問題：ダイクストラ法(1959)
■ 定義：2点間を結ぶ経路のうち，辺の重み(距離)の総和が最小のものを求める
■ ダイクストラ法は，始点から「距離が確定した駅」を波紋のように広げていく貪欲法
■ 重みが非負なら，一度確定した駅の最短距離は二度と更新されない
A
4
計算量
3
S
7
C
2
3
B
S→B→C→T ＝ 7 (最短)
2
T
O(E log V)
多項式時間．全国10,465駅ならミリ秒単位で，
100万ノード規模でも実用的に解ける．


# Page. 11

![Page Image](https://bcdn.docswell.com/page/PER948PLJ9.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
部分構造最適性
最短経路の部分経路は，それ自体が最短経路．S→Tの最短路が駅Xを通るなら，そのS→X区間も必ずS→Xの最短路になっている．
1
だから途中の駅ごとに「ここまでの最短距離」だけ覚えればよい(経路の組合せを列挙しなくてよい)
2
だから一番近い駅から順に確定してよい(貪欲法の正しさが保証される)
3
この性質を使う設計図が動的計画法(DP)．最短経路はDPと相性が最高に良い問題
この「当たり前に見える性質」が，最長経路では成り立たない．
11 /26


# Page. 12

![Page Image](https://bcdn.docswell.com/page/P7XQ28N6EX.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
12 /26
最長経路問題：「同じ駅を二度通らない」が本質
■ 定義：同一の駅を二度通らない単純経路(simple path)のうち，営業キロの総和が最大のものを求める
■ 「単純経路」の制約がなければ，環状線を無限に回れて答えが発散する．制約こそが問題を定義する
■ 鉄道での実例は，改札を出ずに乗れる「最長片道きっぷ」の世界．旅客営業規程にも同じ制約がある
見た目は最短経路の「max版」なのに
目的関数をminからmaxに変えただけで，問題の性質は一変
する．単純経路制約が「どの駅を使ったか」という組合せ的な記
憶を要求するため．
環状線は「一周まで」．二周目は同じ駅を再訪してしまう．


# Page. 13

![Page Image](https://bcdn.docswell.com/page/37K9MKNG7D.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
NP困難となる理由
最長経路の部分経路は，最長経路とは限らない．途中で「寄り道」した方が全体は長くなるが，寄り道に使った駅は後で使えなくなる．
1
「ここまでの最長距離」だけでは足りず，「どの駅を使い済みか」まで覚える必要がある．状態数が2のn乗に爆発する
2
全駅を一度ずつ通る経路(ハミルトン路)の存在判定がそのまま帰着される，古典的なNP困難問題
3
一般グラフでは，多項式時間の厳密解法は(P≠NPなら)存在しない．近似すら困難なクラス
最短経路は「距離」というスカラーの記憶で足りる．最長経路は「集合」の記憶を強いられる．
13 /26


# Page. 14

![Page Image](https://bcdn.docswell.com/page/LJ3WYZV5J5.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
14 /26
計算量の対比
問題
代表的な解法
計算量
全国10,465駅での現実感
最短経路
ダイクストラ法
O(E log V)
ミリ秒．100万ノードでも実用的
最長経路(一般グラフ)
厳密な全探索
指数時間 (NP困難)
そのままでは事実上，解けない
最長経路(DAG)
トポロジカル順のDP
O(V + E)
一瞬．閉路がなければ簡単になる
(参考)巡回セールスマン
実務はGurobi等で近似
O(n!) (NP困難)
50駅の巡回でも厳密解は非現実的
閉路のない有向グラフ(DAG)なら，最長経路はO(V+E)で解ける．この性質が第4部のオントロジーの話で効いてくる．


# Page. 15

![Page Image](https://bcdn.docswell.com/page/8JDK5R8YEG.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
15 /26
先行事例：東京メトロの「改札内最長片道」問題
モバイルファクトリー社 Tech Blog (2018)
全国規模では？
■ 改札を出ずに営業キロの和が最長になる迂回経路を，旅客営業規
■ 駅数10,465，区間11,619．メトロ
程に基づいて定式化
の約60倍のノード数
■ グラフ問題ライブラリGraphillion(ZDDベース)で全経路を列挙し，
■ ZDDによる厳密全列挙は，現実的な
重み最大の経路を厳密に取得
時間で終わらない可能性が高い
■ 改札内乗り換え駅(赤坂見附と永田町など)は距離0の辺で接続し，
■ そこで鉄道網の「構造」を利用した独
並行路線は路線別ノードに分離
自の分解アルゴリズムを設計(第3部)
■ 結果は 和光市 → 西船橋 の78.8km(東京メトロ全179駅の規
模)
出典：モバイルファクトリー Tech Blog「Graphillionで東京メトロの最長経路問題を考える」(2018)．問題定義は本記事に準拠．


# Page. 16

![Page Image](https://bcdn.docswell.com/page/VEPKGW8278.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
16 /26
Microsoft Fabric Apps(プレビュー)とは
■ TypeScriptでデータモデルを宣言するだけで，アプリの基盤一式がFabric上に自動生成される新機能
■ デプロイは npx rayfin up の1コマンド．ビルドしたReactアプリがそのままFabricにホスティングされる
↓ ここから自動生成されるもの
// rayfin/data/schema.ts
@entity()
@authenticated('*')
export class Station {
@uuid() id!: string;
@text({ unique: true }) stationCd!: string;
@text() name!: string;
@decimal() lat!: number;
@decimal() lon!: number;
}
出典：Microsoft Learn の Fabric Apps overview(Rayfin SDK、プレビュー機能)
GraphQL API
Data API Builder互換のクエリ/ミューテー
ション
Fabric SQL Database
スキーマから自動生成(dbo.Stationsなど)
静的ホスティング
*.webapp.fabricapps.net で即公開
Fabric SSO認証
Entra IDベースのサインインが標準装備


# Page. 17

![Page Image](https://bcdn.docswell.com/page/27VV68NX7Q.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
17 /26
全体アーキテクチャ
駅データ.jp
CSV
シードスクリプト
Fabric
SQL Database
Reactアプリ
(Fabric Apps)
station / join
(10,963行 / 10,189行)
mssqlパッケージで
一括bulk INSERT
Stations / StationEdges
/ LongestPathRuns
起動時に全件取得し
グラフを構築
ブラウザ内で完結する計算エンジン(TypeScript移植)
ダイクストラ法(二分ヒープ) / Tarjan橋検出 / block-cut tree分解 / 枝刈りDFS / Color-Coding近似 → Leaflet +
OpenStreetMapで経路を描画
計算結果は「この結果をLakehouseに保存」ボタンからGraphQL mutationで書き込む．Python版パイプライン
(Fabric Notebook 3本)も別途構築済み．


# Page. 18

![Page Image](https://bcdn.docswell.com/page/5JGLN5KR7L.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
18 /26
分解アルゴリズム：NP困難を局所的なブロックに限定する
■ 鉄道網は大部分が支線・盲腸線の「ほぼ木構造」．複数経路があるのは都市部など局所的な範囲だけ
■ Tarjanのアルゴリズムで橋と二重連結成分をO(V+E)で検出する．橋は「必ず通る強制辺」になる
■ ブロック内だけ最長単純路を解き、橋でつなぐ．関節点は二度通れないため，ブロック毎の最適の連結が全体最適になる
橋(強制辺)
橋(強制辺)
S
T
ブロック1：環あり → 探索
ブロック2：環あり → 探索
指数的な難しさは赤いブロックの内部にだけ残る．全国規模でも現実的な時間で解ける．
ブロック3：環あり → 探索


# Page. 19

![Page Image](https://bcdn.docswell.com/page/47QYQZNYEP.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
19 /26
ブロック内部の解き方：厳密解と近似解の二段構え
厳密解
ノード数24以下のブロック
■ 枝刈り付き深さ優先探索(DFS)で全探索
■ 枝刈りその1：残りのグラフで出口に到達できなければ
打ち切り
■ 枝刈りその2：現在距離と残り辺重みの上界の和が
既知の最良解以下なら打ち切り
近似解
大きなブロック(都心部など)
■ Color-Coding法(Alon, Yuster & Zwick 1995)
にフォールバック
■ 駅をランダムにk色に塗り，「色の集合」ごとの最大重
みをDPで追跡する．集合の記憶を色数分に圧縮できる
■ 時間予算内のランダム化DFSヒューリスティックも併用
アプリの結果表示にも「解法：厳密解 / 近似解(Color-Coding)」を明示し，保証の有無を伝えている．


# Page. 20

![Page Image](https://bcdn.docswell.com/page/KE4WN3GZJ1.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
20 /26
最短(緑)と最長(赤)を一画面で対比
地図表示
Leaflet + OpenStreetMap．APIキ
ー不要
オートコンプリート
1万件超の駅名から上位50件を軽量表
示
色分け描画
最短は緑，最長は赤の複数経路レイヤ
都心部を埋め尽くす最長経路(赤)．起点と終点の江古田/新江古田．
Fabric Apps 構築用のリポジトリ
https://github.com/mshdtksk/fabric-longest-path-problem
計算はすべてブラウザ内，
保存はFabricへ


# Page. 21

![Page Image](https://bcdn.docswell.com/page/L71Y51DDJG.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
21 /26
オントロジーは「点と辺のグラフ」である
■ 点は概念(Entity)，辺は関係(Relationship)．近い点は意味が似ており、遠い点は意味が遠い
■ つまり駅とまったく同じ土俵で，グラフアルゴリズムがそのまま適用できる
■ そして，このグラフの構築の仕方そのものが，オントロジーの質を決める
Order
Customer
Route
Shipment
Truck
意味的に遠い(概念距離が大きい)
Invoice
Subscriber
意味的に近い(概念距離が小さい)


# Page. 22

![Page Image](https://bcdn.docswell.com/page/G7WG58Y8E2.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
22 /26
最短経路 × オントロジー：「意味の近さ」を測る
説明可能性
「CustomerとInvoiceはどう繋がる？」に，最短の説明経路で答える．Data Agentが『なぜその回答か』を根拠付きで
示せる
類似概念検索
概念距離が小さいことは，意味が似ていることを表す．CustomerとSubscriberを同義候補として提示できる．セマンテ
ィック検索の土台
メタデータ探索
「売上」という概念から最短で到達できるテーブル・カラム・レポートを提示する．データカタログの動線設計に使える
例：顧客売上を教えて → Customer → Order → OrderLine → Revenue という最短の参照経路が、回答の「説明」になる


# Page. 23

![Page Image](https://bcdn.docswell.com/page/4JZLN8X9E3.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
23 /26
最長経路 × オントロジー：「意味の深さ」を測る
概念階層の深さ
Customer → Premium → Corporate → Strategic のような階層の最長経路長がOntologyDepth．複雑度や
粒度の設計レビュー指標になる
依存チェーン分析
OneLake → Lakehouse → Table → Semantic Model → Report → Data Agent の最長依存鎖は，変更
影響や障害波及の最大経路を表す
RAGの優先検索
深いノードほど具体的で専門的．「ASR9000について教えて」という質問には，階層の深い概念を優先的に検索対象に
できる
概念階層や依存関係は通常DAGになる．鉄道網ではNP困難だった最長経路が，ここではO(V+E)で解ける．


# Page. 24

![Page Image](https://bcdn.docswell.com/page/YE6W8P4DEV.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
24 /26
2つを組合せる：オントロジー品質の定量化
Ontology Health Score ＝ α × LongestDepth ＋ β × AvgShortestPath
LongestDepthは知識の「深さ」，AvgShortestPathは知識の「つながりやすさ」を表す
Critical Path分析
PERT/CPMの発想を流用し，深さ×利用頻度×Agent参照回数で「重要概念」を特定する
中心性との併用
PageRankや媒介中心性を加えて，AIエージェントにとっての要衝概念を発見する
実装イメージ
オントロジーをNetworkXのDAGへ変換し，dag_longest_path()などで算出．Power BIでOntology
Health Dashboardにする
グラフの張り方を「測れる」ようになれば，オントロジーは設計レビューと継続改善の対象になる


# Page. 25

![Page Image](https://bcdn.docswell.com/page/GE5M9KQ8E4.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
25 /26
当初の思想からの道しるべ
経路アルゴリズム
オントロジーの質向上
AIの推論品質向上
ユースケースの自動発掘
最短経路は意味の近さ，
最長経路は意味の深さを測る
測る，見直す，鍛える．
Health Score / Critical Path
Fabric IQとData Agentが
深く正確に業務を辿れる
データ構造から潜在的で
複合的な活用シーンを提案
3年前に描いた「データ活用のユースケース発掘の自律化」
オントロジーが業務コンテキストを担い，グラフアルゴリズムがその質を支える


# Page. 26

![Page Image](https://bcdn.docswell.com/page/97292WPVJR.jpg)

© 2026 NTT West, Inc. All Rights Reserved.
まとめ
最短と最長は似て非なる問題
1
minとmaxの一字違いで，多項式時間とNP困難に分かれる．ただしDAGや分解といった「構造」を見抜けば戦える．
Fabric Apps は，アルゴリズムを「動くアプリ」にする最短経路
2
TypeScriptのスキーマ定義とrayfin upだけで，DB・API・ホスティング・認証が揃う．
オントロジーはグラフであり，経路アルゴリズムがその質を高める
3
意味の近さ(最短)と深さ(最長)を測ることが，ユースケース自動発掘の未来につながる．
26 /26