質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

新規登録して質問してみよう
ただいま回答率
85.54%
グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

Q&A

解決済

2回答

1356閲覧

ダイクストラ法の高速化が出来ない

kay_ventris4

総合スコア269

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。

0グッド

1クリップ

投稿2022/07/28 10:44

編集2022/07/28 14:44

問題

アルゴリズムと数学 演習問題集 80

方針

xをノードA_iとノードB_iで結ばれる長さC_iのエッジからなる無向グラフと考え、ノード0からノード(N - 1)までの最短距離を考える。もしそれがinfなら-1と出力し、そうでないならその距離を出力。

コード

Python

1import heapq 2def dijkstra(graph, N): #ダイクストラ法 #N個の頂点からなるグラフの最短経路 3 dist = [float('inf') for _ in range(N)] 4 dist[0] = 0 5 6 data = [[0, 0]] #未確定ノード[距離, ノード番号] 7 while data: 8 pos = heapq.heappop(data)[1] 9 10 11 for node, cost in graph[pos]: 12 if dist[pos] + cost < dist[node]: 13 dist[node] = dist[pos] + cost 14 heapq.heappush(data, [dist[node], node]) 15 return dist 16 17N, M = map(int, input().split()) 18 19graph = [[] for _ in range(N)] 20for _ in range(M): 21 A, B, C = map(int, input().split()) 22 A -= 1 23 B -= 1 24 graph[A].append([B, C]) 25 graph[B].append([A, C]) 26 27ans = dijkstra(graph, N)[-1] 28if ans == float('inf'): 29 print(-1) 30else: 31 print(ans)

質問

慣れないながらheapを用いてダイクストラ法を実装してみました。テストケースを見ると一つの時間切れ(2000ms超え)を除けば全て正解でした。同じ頂点を何度もみないようにseen配列でそれを管理することで高速化を図ったり(しなかったり)したのですが、尚問題が解決しません。一体どのような箇所に注目して改善すればよろしいのでしょうか。素人質問にて恐縮ですが、お力添えいただける箇所がございましたら、ご教授のほど何卒よろしくお願い申し上げます。

気になる質問をクリップする

クリップした質問は、後からいつでもMYページで確認できます。

またクリップした質問に回答があった際、通知やメールを受け取ることができます。

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

guest

回答2

1

ベストアンサー

手元でいろいろ試したところ、リストをタプルに変更しただけで、倍ぐらい速くなりました。

python

1import heapq 2def dijkstra(graph, N): #ダイクストラ法 #N個の頂点からなるグラフの最短経路 3 dist = [float('inf') for _ in range(N)] 4 dist[0] = 0 5 6 data = [(0, 0)] #未確定ノード[距離, ノード番号] 7 while data: 8 pos = heapq.heappop(data)[1] 9 10 11 for node, cost in graph[pos]: 12 if dist[pos] + cost < dist[node]: 13 dist[node] = dist[pos] + cost 14 heapq.heappush(data, (dist[node], node)) 15 return dist 16 17N, M = map(int, input().split()) 18 19graph = [[] for _ in range(N)] 20for _ in range(M): 21 A, B, C = map(int, input().split()) 22 A -= 1 23 B -= 1 24 graph[A].append((B, C)) 25 graph[B].append((A, C)) 26 27ans = dijkstra(graph, N)[-1] 28if ans == float('inf'): 29 print(-1) 30else: 31 print(ans)

テストデータは、以下のコードで生成したものを使用しました。

python

1N=100000 2graph = [(i, j, (j - i - 1) * 10 + 1) for i in range(5) for j in range(i + 1, N)] 3print(N, len(graph)) 4for i, j, l in graph: 5 print(i + 1, j + 1, l)

投稿2022/07/29 12:31

編集2022/07/29 19:43
actorbug

総合スコア2205

kay_ventris4👍を押しています

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

kay_ventris4

2022/07/29 15:53

リストとタプルのパフォーマンスにおける性能差を知らず調べましたが、このような違いがあったのですね。実際ご提示頂いたコードは、Python3.8.2では時間切れを起こしたものの、Pypy3で1200ms程度で通りました。誠にありがとうございました。
guest

0

全く同一のコードを、C++で提出したところ、2000ms超え → 約800msで通りました。
余程洗練された手法を用いない限りは、Pythonの宿命と受け取るしかないのでしょうか…
解決したとは言えず締め方も非常によろしくないのですが、とりあえず「自己」解決ということで完結させて頂きます。

C++

1#include <bits/stdc++.h> 2#include <math.h> 3using namespace std; 4#define ll long long 5 6/* infinity */ 7ll inf = pow(10, 60); 8 9vector<ll> dijkstra(vector<vector<vector<ll>>> graph, ll N) { 10 vector<ll> dist = {}; 11 for (ll i = 0; i < N; i++) { 12 dist.push_back(inf); 13 } 14 dist.at(0) = 0; 15 priority_queue<vector<ll>, vector<vector<ll>>, greater<vector<ll>>> data = {}; 16 data.push({0, 0}); 17 while (data.size() > 0) { 18 ll pos = data.top().at(1); 19 data.pop(); 20 for (vector<ll> el: graph.at(pos)) { 21 ll node = el.at(0); 22 ll cost = el.at(1); 23 if (dist.at(pos) + cost < dist.at(node)) { 24 dist.at(node) = dist.at(pos) + cost; 25 data.push({dist.at(node), node}); 26 } 27 } 28 } 29 return dist; 30} 31 32void solve() { 33 ll N, M; cin >> N >> M; 34 vector<vector<vector<ll>>> graph = {}; 35 for (ll i = 0; i < N; i++) { 36 graph.push_back({}); 37 } 38 for (ll i = 0; i < M; i++) { 39 ll A, B, C; cin >> A >> B >> C; 40 A--; B--; 41 graph.at(A).push_back({B, C}); 42 graph.at(B).push_back({A, C}); 43 } 44 45 vector<ll> dist = dijkstra(graph, N); 46 47 ll ans = dist.at(N - 1); 48 if (ans == inf) { 49 cout << -1 << endl; 50 } 51 else { 52 cout << ans << endl; 53 } 54} 55 56int main() { 57 solve(); 58}

投稿2022/07/28 14:47

編集2022/07/28 15:15
kay_ventris4

総合スコア269

バッドをするには、ログインかつ

こちらの条件を満たす必要があります。

あなたの回答

tips

太字

斜体

打ち消し線

見出し

引用テキストの挿入

コードの挿入

リンクの挿入

リストの挿入

番号リストの挿入

表の挿入

水平線の挿入

プレビュー

15分調べてもわからないことは
teratailで質問しよう!

ただいまの回答率
85.54%

質問をまとめることで
思考を整理して素早く解決

テンプレート機能で
簡単に質問をまとめる

質問する

同じタグがついた質問を見る

グラフ理論

グラフ理論とは、頂点(node)と辺(edge)で構成されたグラフに関する数学理論で、グラフの多様な性質を探求することを指します。グラフは、頂点と向き(矢印)を持つ辺で構成された有向グラフと、矢印のない無向グラフに分類。さまざまな日常の場面で使用することを目的としている理論です。

アルゴリズム

アルゴリズムとは、定められた目的を達成するために、プログラムの理論的な動作を定義するものです。

Python

Pythonは、コードの読みやすさが特徴的なプログラミング言語の1つです。 強い型付け、動的型付けに対応しており、後方互換性がないバージョン2系とバージョン3系が使用されています。 商用製品の開発にも無料で使用でき、OSだけでなく仮想環境にも対応。Unicodeによる文字列操作をサポートしているため、日本語処理も標準で可能です。