📖

グラフ(応用)Warshall-Floyd, 0-1 BFS

LeetCode 練習問題集

問題
難易度
重要度
テクニック
★★★★
Warshall-Floyd
★★★★
0-1 BFS
★★★★
0-1 BFS
★★★★
0-1 BFS

Warshall-Floyd(ワーシャルフロイド)

事前に必要な知識
  • 動的計画法の基礎
ワーシャルフロイドは全点対間最短経路問題を効率的に解くアルゴリズムです。全点対間最短経路問題とはその名前の通り全てのノード同士の最短距離を求める問題です。
全点対間最短経路問題はダイクストラを使用しても解くことが可能です。ダイクストラでは決まったあるノード(始点)から他の全てのノードへの最短距離をまたはで求めることができます。これを全てのノードに対して実行することでまたはで全点対間最短経路問題を解くことができます。
これに対してワーシャルフロイドはで全点対間最短経路問題を解くことができます。以上より、グラフが疎でも密でもダイクストラを使用しても問題はありません。ですが密グラフにおいてはワーシャルフロイドの使用をお勧めします。理由としてはワーシャルフロイドのコード自体はとてもシンプルなものだからです。実際に例題を通して全点対間最短経路問題をワーシャルフロイドで解いてみましょう。
すべてを見るには

返金は購入日から1日以内に申し出て下さい。詳細はこちらからご確認ください。
また、このコンテンツ以外の他の永久アクセス権は付与されない事はご注意下さい。

支払いはによって保護されています

購入済の方はこちらからログインしてください

テック企業求人一覽

こちらの求人をrecoから紹介されたものです。 recoは現役の外資エンジニアがモックインタビュー付きで面接対策を行ってくれる転職サービスです。 これらの企業にどのように準備に準備して振る舞えば採用されるのか的確なアドバイスを受ける事ができます。 InterviewCatの共著者のgaijineersさんが創業者として皆さんの転職をサポートします。

Mercari
Software Engineer, Backend - Mercoin
Go
Web application development
API development
Protocol Buffers
gRPC

Mercari

Mercari
Software Engineer, iOS - Merpay
UIKit
SwiftUI
Protocol Buffers
Bazel
CircleCI

Mercari

Mercari
Software Engineer, QA - Merpay/Mercoin
QA
Mobile App
Web App
Testing Technology
Testing Automation

Mercari

LegalOn Technologies
TECH-101- Software Engineer, Backend
Go
Docker
Java
AWS
Python

年収: 6501070万円

LegalOn Technologies

LegalOn Technologies
TECH-102- Senior Software Engineer, Backend
Webバックエンド
Linux OS
リレーショナルデータベース
Web API
キャッシュ

年収: 10301500万円

LegalOn Technologies

LegalOn Technologies
TECH-301- Software Engineer, Frontend
Webフロントエンド
TypeScript
HTML
CSS
JavaScript

年収: 7701500万円

LegalOn Technologies

LegalOn Technologies
TECH-MI-101- Software Engineer, LegalOn Technologies Research
AI
Machine Learning
Natural Language Processing
Web Development
Software Development

年収: 7701500万円

LegalOn Technologies

LegalOn Technologies
TECH-NP-104 Senior Software Engineer, Frontend Lead - New Product
React
Next.js
TypeScript
Webpack
Vite

年収: 7701800万円

LegalOn Technologies

LegalOn Technologies
TECH-S-101- Software Engineer - Search
プロダクトマネージャー
テックリード
プロジェクトリーダー
データ構造
アルゴリズム

年収: 7701070万円

LegalOn Technologies

LegalOn Technologies
TECH-S-102- Senior Software Engineer - Search
検索
推薦

年収: 10301500万円

LegalOn Technologies

LegalOn Technologies
TECH-S-103- Software Engineering Manager - Search
検索
推薦
マネジメント
機械学習
自然言語処理

年収: 14402500万円

LegalOn Technologies

LegalOn Technologies
TECH-S/EN-103- Software Engineering Manager - Search
Python
Java
SQL
gRPC
Kubernetes

年収: 14.425万円

LegalOn Technologies

LegalOn Technologies
TECH-US-101- Software Engineer, Backend - Global Team
Ruby
AWS
Docker
DDD
Clean Architecture

年収: 7701070万円

LegalOn Technologies

LegalOn Technologies
TECH-US-102- Senior Software Engineer, Backend - Global Team
Ruby
AWS
GCP
Azure
Docker

年収: 10701500万円

LegalOn Technologies