Hatena Blog Tags
はてなブログ トップ
Dijkstra
このタグでブログを書く
言葉の解説
ネットで話題
関連ブログ

Dijkstra

(コンピュータ)
【だいくすとら】
このタグの解説についてこの解説文は、すでに終了したサービス「はてなキーワード」内で有志のユーザーが作成・編集した内容に基づいています。その正確性や網羅性をはてなが保証するものではありません。問題のある記述を発見した場合には、お問い合わせフォームよりご連絡ください。
競プロをする奴•2年前

E - Two Currencies(解説)

[解法] 結論から言えば、拡張ダイクストラというものをする。なにを拡張するのかというと、ノードの数である。 そもそもダイクストラをただ単に移動する最短距離や最小コストを得るものとして捉えるのではなく、 最初の状態から最後の状態 になるための最小コストを得るものだ と捉えてほしい。 ある点からある点への移動 はもっと抽象的にいうと ある状態からある状態への推移 と捉えることができる。 今の状態から次にどのような状態にすることができるかを考えれば、自然にダイクストラを拡張することができる。 今回は、 [街Uにいるときに銀貨をx枚もっている] というものを一つの状態にすることができる。 街Uからは街…

#ダイクストラ#Dijkstra#拡張ダイクストラ

ネットで話題

もっと見る
147ブックマークPython を Go に書き換えるとどれくらい速くなる？ 7つの言語で Dijkstra の実行速度を比較 - Qiitaqiita.com
26ブックマークE.W.Dijkstra Archive: Home pagewww.cs.utexas.edu
19ブックマークFamily Collection Dijkstra vai avanti .com by rafaël rozendaal, 2006VAI AVANTI .COM BY RAFAEL ROZENDAAL - 2006 - WWW.NEWRAFAEL.COM, FAMILY COLLECTION DIJKSTRA, CODE BY REINIER FEIJEN - WWW.BOXOFCHOCOLATES.NLwww.vaiavanti.com
10ブックマーク文系 Hadooper でも分かる Dijkstra アルゴリズム - cocoatomo衝動日記〈移行後版〉cocoatomo.hatenablog.jp
10ブックマークE.W.Dijkstra Archive: The Humble Programmer (EWD 340)The Humble Programmer by Edsger W. Dijkstra As a result of a long sequence of coincidences I entered the programming profession officially on the first spring morning of 1952 and as far as I have been able to trace, I was the first Dutchman to do so in my country. In retrospect the most amazing t...www.cs.utexas.edu
9ブックマーク2011年4月/03 [Sun]@14:37 きょう気づいたが、dijkstraの例の文章を以前に (新山とはまったく独立に) 翻訳してた人がいたらっし。しかし彼の訳文は (新山にとっては) 日本語としてほとんど理解不/29 [Fri] @09:39 とある会社のパスワード変更規則だと。 ******************************************************************** ** STOP! パスワードを再設定してください。 ** そうしないとあなたのネットワークアカウントは使用不能になります。 ****************************************************************...tabesugi.net
8ブックマークE.W. Dijkstra Archive: Why numbering should start at zero (EWD 831)Are there reasons to prefer one convention to the other? Yes, there are. The observation that conventions a) and b) have the advantage that the difference between the bounds as mentioned equals the length of the subsequence is valid. So is the observation that, as a consequence, in either convent...www.cs.utexas.edu
7ブックマークGitHub - ibaaj/dijkstra-cartography: Using Dijkstra's algorithm ("finding the shortest paths between nodes in a graph") to draw maps .github.com
7ブックマークDijkstra was right — recursion should not be difficultblog.angularindepth.com

関連ブログ

元Webデザイナー兼コーダーの備忘録•3日前

構造化プログラミング:概要

構造化プログラミング*1とは、コードの書き方のことです。 プログラムの基本構文は分かるが、どのようにコードに落とし込んだら良いのか悩んでいる方がいましたら、本記事を参考にしてみてください。プログラムの書き方のヒントになれば幸いです。 今回は、構造化プログラミングの概要について書きます。ついでに構造化プログラミング以前のコードの書き方についても少しだけ触れておきます。ソフトウェア開発の歴史のお話です。 構造化プログラミングの3つの制御構造 順次 分岐 反復 構造化プログラミング以前のコードの書き方 goto文:無条件分岐文 まとめ 構造化プログラミングの3つの制御構造 構造化プログラミングでは、…

あめんばーどのバーチャル日記•6日前

【競プロ】作問振り返りメモ

無事コンテストが終わることができて良かったですが、その上で反省点も非常に多い作問でした。 思い出としての振り返りもいっぱいあるんですが、それは別の記事にすることにして当記事につきましては作問にあたっての反省点や留意点をまとめていけたらと思います。 反省と言う割には、結構文章は適当です。苦手なので。

nakorakeの日記•7日前

Pythonによる実務で役立つ最適化問題100+ (1): グラフ理論と組合せ最適化への招待

昨日読了。 Pythonによる実務で役立つ最適化問題100+ (1): グラフ理論と組合せ最適化への招待 作者:久保 幹雄 朝倉書店 Amazon 辞書。 辞書なので、パッと読んで、知らないこと・後からよく調べたいことをメモ。 Hamilton閉路。すべての頂点を１回ずつ通る閉路。Hamilton閉路の距離最小のものが、巡回セールスマン問題の最適解である。 Steiner木。頂点の部分集合（ターミナル）をつなぐ最小距離の木を求める。ターミナル以外の頂点は使っても使わなくてもよい。NP困難。 クリーク。頂点の部分集合で、完全グラフを構成するもの。最大クリーク問題と、最大安定集合問題（安定集合は頂…

myauの競プロブログ•13日前

ABC302 参加記

7完64:09 149位 Eで多少詰まったけどFGをまあまあの速度で通せてセーフ A Attack 切り上げは (A + B - 1) / Bでできるやつ Aでforが出るならlong long もでていいよね (AC 2:54) B Find snuke 250点はなんだと思ってみると重実装がおいてある とはいっても、楽することはできて dx = {-1, 0 , 1} dy = {-1, 0, 1} の全組み合わせを、すべてのマスを始点として試せばよいです 8方向書くときには↑のような定義おすすめです(dx = dy = 0は適切に省く) (AC 8:12) C Almost Equal …

コミュ障だから明日が僕らをよんだって返事もろくにしなかった•15日前

今の心境

どうしたものかと考えても何もできない ピンチをチャンスにとかそんな言葉があるじゃないですか。そういうのの先って闇バイトとしかないんですよね。このブログを読んでいるみなさまはまともな人間なのでまた違った選択肢もあるのでしょうけども僕にはそういうのはないのでもうダメです。 まあそんな話はいいや。 こういったサイトがあった。 Family Collection Dijkstra vai avanti .com by rafaël rozendaal, 2006中身はこういったやつ。疑似３D味ある何か。 つまりどういったことかと言われたらどういうものかはわからない

けんちょんの競プロ精進記録•21日前

AOJ 2567 SIRO Challenge (JAG 模擬地区 2013 C) (400 点)

「ABC 301 E - Pac-Takahashi」の類題とも言うべき ICPC 系の問題！ 問題へのリンク (AOJ) 問題へのリンク (AtCoder) editorials 問題概要 頂点数 、辺数 の重み付き無向グラフが与えられる。頂点番号は とする。 番目の辺は頂点 を結んでおり、その重みは である。 このグラフの頂点のうち 個の特別な頂点 があって、その頂点には SIRO というラーメン店がある。これらの頂点に立ち寄ったとき、ラーメンを食べるのに要する時間は である。 さて、あなたは今、頂点 にいる。いまからあなたは 秒以内にグラフを移動して、できるだけ多くの SIRO のある頂…

"Truth of the Legend" Notes•22日前

論文：ELIZA ー 人間と機械の自然言語コミュニケーション研究のためのコンピュータプログラム

ELIZA -- A Computer Program For the Study of Natural Language Communication Between Man And Machine Joseph Weizenbaum Massachusetts Institute of Technology Department of Electrical Engineering Cambridge, Mass.. Communications of the ACM Volume 9, Number 1 (January 1966): 36-35. Abstract（要約） ELIZA is…

kotatsugameの日記•1ヶ月前

週記（2023/05/01-2023/05/07）

05/01(月) 午後1時半起床。しばらく布団でスマホを触った後、起き上がって購買に行きラノベを受け取ったりパン類を買い込んだりした。そこそこ遅めの時間に行ったのに大量に売れ残っていてびっくり。大型連休を前に学生が少なくなっているのだろう。自分はたくさん買えてほくほく顔だった。 しばらく週記を書いた後午後4時半からインターン先定例会に参加した。先週の進捗は1on1でタスクを確認したのと少し作業しただけ。 勉強会は3DCGの仕組みについてだった。この勉強会のために自分でプログラムを書いてモデルの表示やシェーディング、テクスチャー貼り付けなどできるようにしたらしく、その熱意に感服。特にシェーディン…

Moyazine•1ヶ月前

ChatGPTと行くIT世界の旅 #26: ダイクストラ法

今日の記録。 1. Please explain Dijkstra's algorithm in a way that even elementary school students can understand. 2. Explain how Dijkstra's algorithm works 3. What is the time complexity of this algorithm? Dijkstra's algorithm 4. Please visually explain Dijkstra's algorithm 5. Explain applications and use…

よしたろうブログ•2ヶ月前

リファクタリング入門 ~凝集度・結合度~

ランキング参加中プログラミング 凝集度と結合度は、保守性と生産性の高いコードを書くための尺度。凝集度と結合度は順次、選択、反復という要素を持った構造化プログラミングをベースとしている多くの言語に適用できる概念。 1. リファクタリングの必要性 1-1. リファクタリング：動作を変えず内部構造を改善する 1-2 良いコードとは：リファクタリングで目指すもの 1-3. 構造化プログラミングとは：良いコードを書くための普遍的な手法 1-4. 設計やアーキテクチャへの向き合い方：凝集度、結合度を学ぶ前に 2. 凝集度 2-1. 偶発的凝集:無作為に処理が集められた関数 2-2. 論理的凝集:関連のない…

kotatsugameの日記•2ヶ月前

週記（2023/04/03-2023/04/09）

04/03(月) 頭の痒みで飛び起き、シャワーを浴びてまたすぐ寝た。午後1時くらいだった。 午後4時半ちょっと前に起床し、すぐにインターン先定例会に参加した。先週はちゃんとコードを書いたのでそれを報告。他の方が報告している間は聞きながら勉強会スライドの仕上げをしていた。 午後5時過ぎから勉強会。発表と質疑応答がそれぞれ1時間くらいだった。終了後にスライドを公開した。 勉強会0403.pdf - Google ドライブ 勉強会をしました。今日のテーマは「ACLにおける定数倍高速化」です。スライドを公開します。https://t.co/UCxyBozKzf— こたつがめ (@kotatsugame…

Moyazine•2ヶ月前

ChatGPTと行くインフォメーションテクノロジーの旅 #9 ハッシュテーブル

Introduction: Overview of Heap Data Structures: Use Cases for Heap Data Structures: Code Example 解説 Q1. shift_upメソッドの解説 Q2. 配列要素の入れ替え Q3. どのような原理で入れ替えている Q4. @heapの@はどういう意味？ Q5. @heapとheapは何が違うの？ Q6. code snippetの意味を教えて Introduction: Heap are an essential concept in computer science and have a wide …

3度目のサザンドラ•2ヶ月前

【アークナイツ】ストーリー考察/感想 - 翠玉の夢 編

2023年3月14日開始のイベント「翠玉の夢」のストーリーを整理していきます。 1.ライン生命の基礎知識 1-1. ライン生命の10課 1-2. ローキャン水槽ラボの終焉 1-3. サイレンスと9号デバイス 1-4. 炎魔計画 1-5. 炎魔事件の集結 2.イベント時系列 2-1. ドロシーの実験 2-2. ミュルジスのSOS 2-3. 359号基地と開拓隊 2-4. 銀色の液体とは何か 2-5. 酔っぱらった男の残した情報 2-6. クリステンの居場所 2-7. 「覚醒」との戦い 2-8. フェルディナンドの末路 2-9. ホルハイヤの正体 1.ライン生命の基礎知識 背景知識として、ライン生…

PyDocument•2ヶ月前

ダイクストラ法の解説とPythonでの実装例

ダイクストラ法は、グラフ上の最短経路問題を解くためのアルゴリズムの一つです。具体的には、与えられた始点から各頂点への最短距離を求めることができます。以下では、ダイクストラ法のアルゴリズムと、Pythonでの実装を行います。 ダイクストラ法のアルゴリズム このアルゴリズムは、貪欲法に基づいています。具体的には、始点から各頂点への最短距離が確定した頂点集合Sに含まれない頂点のうち、始点からの距離が最小のものを選び、その頂点をSに加えていくことで、最短距離を更新していくというアプローチを取ります。 ダイクストラ法は以下のような手順で動作します。 初期化 スタート地点から各頂点までの最短距離を無限大、…