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

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

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

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

アルゴリズム

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

Python

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

解決済

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

kay_ventris4
kay_ventris4

総合スコア263

グラフ理論

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

アルゴリズム

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

Python

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

2回答

0リアクション

1クリップ

547閲覧

投稿2022/07/28 10:44

編集2022/07/28 14:44

問題

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

方針

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

コード

Python

import heapq def dijkstra(graph, N): #ダイクストラ法 #N個の頂点からなるグラフの最短経路 dist = [float('inf') for _ in range(N)] dist[0] = 0 data = [[0, 0]] #未確定ノード[距離, ノード番号] while data: pos = heapq.heappop(data)[1] for node, cost in graph[pos]: if dist[pos] + cost < dist[node]: dist[node] = dist[pos] + cost heapq.heappush(data, [dist[node], node]) return dist N, M = map(int, input().split()) graph = [[] for _ in range(N)] for _ in range(M): A, B, C = map(int, input().split()) A -= 1 B -= 1 graph[A].append([B, C]) graph[B].append([A, C]) ans = dijkstra(graph, N)[-1] if ans == float('inf'): print(-1) else: print(ans)

質問

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

以下のような質問にはリアクションをつけましょう

  • 質問内容が明確
  • 自分も答えを知りたい
  • 質問者以外のユーザにも役立つ

リアクションが多い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

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

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

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

下記のような質問は推奨されていません。

  • 間違っている
  • 質問になっていない投稿
  • スパムや攻撃的な表現を用いた投稿

適切な質問に修正を依頼しましょう。

まだ回答がついていません

会員登録して回答してみよう

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

ただいまの回答率
87.20%

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

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

質問する

関連した質問

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

グラフ理論

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

アルゴリズム

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

Python

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