YoshikuniJujo on Nostr: ダイクストラ法の実装を修正した。2つの方向で修正した。 ...
ダイクストラ法の実装を修正した。2つの方向で修正した。
ひとつめとしては、オリジナルのダイクストラ法のロジックを踏襲するもので、O(V ^ 2)になる。
この場合、コードはかなりimperativeなものになる。
ふたつめは、ヒープを使う方法。これだとO((V + E) log V)になる。密なグラフだとEがO(V ^ 2)になるので、O(V ^ 2 log V)になって、実行効率はわずかに低下する。
ヒープにはskew heapを使用した。
Published at
2024-08-09 04:30:37Event JSON
{
"id": "72b5f3973035c7fd35af89b11c4ecc888773339b5dbab9a5c2f49081c76133ee",
"pubkey": "ef89ee45550f7377284d31e49fc57e5732ffc2b95a7bf35d0f1291d6fa278758",
"created_at": 1723177837,
"kind": 1,
"tags": [],
"content": "ダイクストラ法の実装を修正した。2つの方向で修正した。\n\nひとつめとしては、オリジナルのダイクストラ法のロジックを踏襲するもので、O(V ^ 2)になる。\nこの場合、コードはかなりimperativeなものになる。\n\nふたつめは、ヒープを使う方法。これだとO((V + E) log V)になる。密なグラフだとEがO(V ^ 2)になるので、O(V ^ 2 log V)になって、実行効率はわずかに低下する。\nヒープにはskew heapを使用した。",
"sig": "dae144125659e8fc8ba19aea1f7ed45b5c671f59a5a633ec60507051b26d2da80361fe9b9b77d9245b24be5c8139c086b98f57402679f53ea825a6583196e381"
}