Dijkstraて

Question

非負実数につかえないのて
優先度つきキュー（ヒープ）からpopしちゃうから
その後に後から更新されないからですか？それって
foreach neighbor v of u: 
のところでQにまだはいってるのじゃなくて
グラフの構造からすべての隣接ち頂点を見るようにすれば解決しませんか？
そういうわけでもないと思いますがあまり考えると悩みそうで時間かかりそうだら
一緒に考えてください。（並列処理）T・T

https://stackoverflow.com/questions/13159337/why-doesnt-dijkstras-algorithm-work-for-negative-weight-edges

cametan_42 · Accepted Answer

英語は得意なのかね。やっぱり帰国子女なのかいな。

ダイクストラ法でエッジの重みに非正数が使えないのは、単に正数を想定したアルゴリズムだから(笑)。単にそれだけ(笑)。他に特に深い理由はないでしょ(笑)。
今だとグラフ、って言ってるけど、そもそもダイクストラがこのアルゴリズムを考えた時って「最短経路問題」を考えてたから、でしょう。「最短距離」だよ?実用的な意味で「長さが負」とかありえないでしょ(笑)。貴女の家から学校までの距離が−500m、とかどんな状態なんだ、と言う(笑)。
基本的にプログラミングは「応用数学」(Applied Mathematics)だから、あくまで「実用範囲」の計算の話になる。厳然とした数学上のグラフでは「負の重み」は理論上アリえても、ある程度「制限を付けた話」がプログラムでの実用上の話になる。

なお、ダイクストラ法は重みが正数、って前提だけど、負数でも使えるアルゴリズムはまた別にあって、貴女がどうしても負数の重みを用いたい、って言った場合はダイクストラ法じゃなくってそっちのアルゴリズムを採用すりゃあエエ話です。

Bellman–Ford algorithm:
https://en.wikipedia.org/wiki/Bellman%E2%80%93Ford_algorithm

cametan_42 · Answer

> どういうところですか？

例えば前の質問のタイトルとか?

「どちのほうがすきですか？」

You wrote どち、but the correct way to write down is "どっち".
However, I know "っ" is very difficult to be distinguished for English speakers.
Thus, you apparently have characteristics of English (or European language) speakers have, which pointed out you are very close to an English-is-a-native-tongue lady, when you write as you speak.

> 関数型言語？はすごい難しそうだし頭いい人しか使えないと思います。

いや、これは逆かな。関数型言語の方が簡単です。
関数型言語を「難しい」って言う人って、単に思考形式が、例えばCとかの「手続き型」の方に慣れちゃったから、なの。
むしろ初心者に近い時点の方が関数型言語の方が色々とラクです。「貴女の思い通りにプログラムが書ける」。

もう一つはね。例えば貴女が「ゆゆにゃ指向プログラミング言語」ってのを作ろうとするじゃない?どういう形式か知らんが(笑)。Yuyunya Orientated Programming Language、YOPだ(笑)。
でもさ、「新しく形式を立ち上げる」って事は「より簡単にプログラム出来るようにする為」なんだよ(笑)。でしょ?「前よりも難しくプログラムするように作ろう!」とか言う人は一人もいないわけだから。
オブジェクト指向だって、「手続き型でプログラムするのが難しい」トコを簡単にする為に作られたんだ・・・それが成功してるかどうか、って判断はまた別だけどね。
よって関数型プログラミングは「手続き型やオブジェクト指向でプログラミングする難しさをより簡単にする」為にある。つまり、「もっと簡単だ」ってのが正解なの。

※: とは言いながら、実は「関数型言語」は尤も古い形式のプログラミングスタイルの一つではある・・・ここでも「関数型プログラミング」は新しかった為、登場当時の「Fortran Style」に慣れていたプログラマの不興を買ってる(笑)。
要は、実は単に「慣れの問題だ」ってのが一番大きい。

> ハスケルは圏論つかうとか聞いたことあります。めちゃ難しそうで全然想像できない。。

うん。まぁ、Haskellは「やり過ぎ」ではあるんだよね(笑)。
ええと、あとでもう一つの質問の方に書こう、って思って準備してるんだけど、ザックリと。
In Computer Science, assignment(代入) and Input-and-Output(入出力) are not CALCULATION. They are called side-effects(副作用)。
Side-effects are necessary around programming. But they are not acceptable as "Mathematically" functions. So Haskell guys were trying to let them be in Mathematical context.....
That's where MONAD comes from, by using a complex "category theory"(圏論).
However, remember not all functional programming guys agree with Haskell style, or purely functional programming language. Almost all functional programming languages except Haskell and a-likes accept side-effects. They are called "impure" functional languages.
OCaml and Microsoft #F are "impure" ones. So, don't be afraid. No Monad, No category theory.

> たしかにパイソンはみんな簡単って言うけどめちゃ簡単ってわけじゃないと思います。

そう、歴史的に見ると、Pythonってどんどん難しくなってんだよ(笑)。まぁ、「言語が進化する」ってのはそういう事でもあるんだけど、ぶっちゃけJava化してる(笑)。Too complex to be understood by newbiesだ。

> まだ変ですか？？

いや、今回はかなり大丈夫です(笑)。

cametan_42 · Answer

> 帰国子女てほど海外にいませんけど半分アメリカです。

ああ、やっぱそうか。
If you preferred, I would use English to write to you. I do not know if my fuckin' English is acceptable or not...

A girl appeared here almost one year ago reminds me the possibility that you are a sort of returnee. Generally speaking, writing Japanese is somehow difficult to do for returnees(especially 漢字! as you guess).
I think you can sometimes post the questions written in English if you are better at. Do not be afraid to do so 'cause now we have A.I. translating tools such as ChatGPT, or whatsoever, which conveniently support us. No problemo. Hasta la vista, baby. Great technology at 2024. Sooner would come Skynet. You are gonna reprogram a Terminator.

Well, I am not a scientist at all. I am a user of a functional programming language(関数型プログラミング言語), which you asked before. "Referential Transparency(参照透過)", "Co-recursion(余再帰)", and "Lazy Evaluation(遅延評価)"... do you remember these terms? The way I program is related to these kinds of things.
To be honest, Python is no longer a good programming language for beginners. I know a bunch of people say "Python is simple to learn"; however, when they say so, they recall a "particular Python" when they learned. In the most cases, they assume Python 2.x. in their mind. In contrary, Python 3.x became much complex. As you said, Python 3.x is entirely covered with a bunch of iterators, which is conceptually incomprehensive for newbies.
Of course, iterators are powerful and useful; however, Python seems to become some kind of an ad-hoc language. In other words, Python is no longer consistent.
If you are serious at programming, you had better to learn a functional programming language, such as Ocaml or F#, which is consistent. You have seemed interested in the Math area; therefore, this kind of tools would also help you much.
A functional programming language is much more advanced, easier to program, powerful, and highly descriptive. You will learn a bunch of concepts, techniques and new points of view of programming and algorithm.

In Japan, the book below is a good tutorial for functional programming:

プログラミングの基礎:
https://www.saiensu.co.jp/search/?isbn=978-4-7819-1160-1&y=2007

This text book is being used in Ochanomizu University.
In addtion to that, you may watch video lectures using this text book here:

「プログラミングの基礎」を使った授業紹介:
http://pllab.is.ocha.ac.jp/~asai/book-mov/

You may find the lecture around Dijkstra's algorithm you mentioned here.

I hope these things help you.

Dijkstraて

英語は得意なのかね。

> どういうところですか？

> 帰国子女てほど海外にいませんけど半分アメリカです。

似たような質問が見つかりました

このQ&Aを見た人はこんなQ&Aも見ています

関連するカテゴリからQ&Aを探す

このQ&Aを見た人がよく見るQ&A

デイリーランキングこのカテゴリの人気デイリーQ&Aランキング

マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング