উভয়ই একটি ওজনযুক্ত গ্রাফে একটি উৎস থেকে সংক্ষিপ্ততম পথ খুঁজে পায়। Dijkstra দ্রুত কিন্তু অ-ঋণাত্মক ওজনের প্রয়োজন; Bellman-Ford ধীরতর কিন্তু ঋণাত্মক প্রান্ত পরিচালনা করতে পারে এবং ঋণাত্মক চক্র সনাক্ত করতে পারে।
বারবার নিকটতম অপরিদর্শিত নোড প্রসারিত করুন এবং এর প্রতিবেশীদের শিথিল করুন।
import heapq
def dijkstra(graph, src):
dist = {n: float('inf') for n in graph}
dist[src] = 0
pq = [(0, src)] # (distance, node)
while pq:
d, u = heapq.heappop(pq) # closest first
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]: # relax edge
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
সমস্ত প্রান্ত V-1 বার শিথিল করুন; আরও শিথিলকরণ মানে একটি ঋণাত্মক চক্র আছে।
| | Dijkstra | Bellman-Ford | |---|---------|| | ওজন | অ-ঋণাত্মক | যেকোনো (ঋণাত্মক সহ) | | সময় | O((V+E) log V) | O(V·E) | | ঋণাত্মক চক্র | প্রযোজ্য নয় | সনাক্ত করে |
অ-ঋণাত্মক ওজনের জন্য ডিফল্টরূপে Dijkstra ব্যবহার করুন (মানচিত্র, নেটওয়ার্ক)। ঋণাত্মক প্রান্ত বিদ্যমান থাকলে Bellman-Ford ব্যবহার করুন (উদাহরণ: মধ্যস্থতা)। Dijkstra ঋণাত্মক ওজনে নীরবে ভেঙে যায় — একটি ক্লাসিক ফাঁদ।
সংক্ষিপ্ততম-পথ অ্যালগরিদম রুটিং, নেভিগেশন, নেটওয়ার্ক প্রোটোকল এবং নির্ভরতা খরচ বিশ্লেষণ চালায়।
Dijkstra-তে অ-ঋণাত্মক-ওজন সীমাবদ্ধতা জানলে ক্ষেত্রে ভুল উত্তর প্রতিরোধ করা যায়।
শিথিলকরণ ধারণা গ্রীডি এবং ডিপি চিন্তাভাবনা সংযুক্ত করে, এটিকে একটি সমৃদ্ধ সিনিয়র-স্তরের বিষয় করে তোলে।