Her yönüyle Dijkstra Algoritması | En kısa yolu bulma

Dijkstra'nın algoritması, bir graf içindeki en kısa yolun bulunması için kullanılan bir algoritmadır. Genellikle ağırlıklı graf (weighted graph) olarak adlandırılan, yani her kenarın bir ağırlığı veya maliyeti olan graf yapıları üzerinde çalışır.

00:00 Giriş - Dijkstra'nın algoritması nedir?
04:33 PriorityQueue çalışma mantığı
07:54 Dijkstra içerisinde PriorityQueue kullanımı
17:21 C# kodu
24:43 Leetcode soruları
25:24 Dezavantajları
27:52 Algoritma öğrenmenin en iyi yolu

Algoritmanın işleyişi şu şekilde:

1. Başlangıç node'u seç. Bu node'a olan uzaklığı 0 olarak ayarla, diğer node'lara olan uzaklıkları sonsuz (∞) olarak kabul et.

2. Başlangıç node'undan başlayarak, henüz ziyaret edilmemiş node'lara doğru ilerle. Her adımda, şu anda ziyaret edilen node'un komşularını kontrol et.

3. Ziyaret edilmemiş komşu node'u, ziyaret edilen node'a olan uzaklıkla birlikte hesapla. Eğer yeni hesaplanan uzaklık, daha önce kaydedilen uzaklıktan daha küçükse, bu yeni değeri kullan ve node'u ziyaret edilen node olarak kaydet.

4. Tüm komşuları kontrol ettikten sonra, ziyaret edilen node'u işaretli olarak işaretle ve bir sonraki adıma geç.

5. Başlangıç node'unda diğer tüm düğümlere olan en kısa yollar hesaplanana kadar adımları tekrarla. Her adımda, en küçük uzaklığa sahip olan ziyaret edilmemiş node'u seç.

6. Algoritma tamamlandığında, başlangıç node'undan diğer tüm node'lara olan en kısa yollar hesaplanmış olur.

Bu şekilde Dijkstra'nın algoritması, graf içindeki en kısa yolu bulmak için kullanılır. Algoritmanın temel fikri, başlangıç node'undan her bir noda'a olan en kısa yolu aşamalı olarak hesaplamaktır. Algoritma, genellikle priority queue veri yapısını kullanarak en küçük uzaklığa sahip node'ları seçer ve işaretler. Bu sayede, daha kısa yollar daha önce hesaplanır ve sonunda en kısa yol elde edilir.

Peki dezavantajları?

Negatif ağırlıklara sahip kenarlarla başa çıkamaz: Dijkstra algoritması, negatif ağırlıklara sahip kenarlara sahip grafiklerde doğru sonuçlar üretemez. Algoritma, işlediği node'ları işaretleyerek ve uzaklık değerlerini güncelleyerek çalışır. Negatif ağırlıklara sahip bir kenar, daha kısa bir yol bulmak yerine Dijkstra algoritmasını döngülere sürükleyebilir.

Yavaş çalışabilir: Dijkstra algoritması, tüm node'lar üzerinde gezinme gerektiren bir algoritma. Bu nedenle, grafikteki node sayısı arttıkça ve ağırlıklar karmaşık hale geldikçe, algoritmanın çalışma süresi artar. Özellikle büyük grafiklerde veya yoğun ağlar içeren durumlarda performans sorunları olabilir.

Her seferinde tüm node'lara bakar: Dijkstra algoritması, en kısa yolun bulunması için her adımda tüm node'ları ziyaret eder. Bu, daha büyük graflarda ve karmaşık ağlarda verimsiz olabilir. Eğer sadece belirli bir hedef düğüme kadar olan en kısa yolları bulmak istiyorsanız, Dijkstra algoritması gereksiz işlemler yapmış olur.

Daha karmaşık durumlar için, negatif ağırlıklarla başa çıkabilen veya daha hızlı sonuçlar üreten alternatif algoritmalar mevcut, örneğin Bellman-Ford algoritması veya A* arama algoritması gibi.

Referanslar:

Dijkstra algoritması:

https://en.wikipedia.org/wiki/Dijkstr...
https://algs4.cs.princeton.edu/44sp/

C# PriorityQueue:

https://learn.microsoft.com/en-us/dot...

Leetcode soruları:

https://leetcode.com/problems/network...
https://leetcode.com/problems/swim-in...
https://leetcode.com/problems/path-wi...

#algoritmalar #yazılım #programlama

***

🤖 LEETCODE ►    • Leetcode  
💚 HACKERRANK ►    • Hackerrank  
👌 HACKERRANK- 30 DAYS OF CODE ►    • Hackerrank - 30 Days of Code  
🎁 C# YENİLİKLERİ ►    • C#  
💜 SIFIRDAN C# PROGRAMLAMA EĞİTİMİ ►    • Sıfırdan C# Programlama Eğitim Seti  
🔆 C# SHORTS ►    • Shorts  
🎨 .NET YENİLİKLERİ ►    • .NET  
⭐ .NET MAUI VİDEOLARI ►    • .NET MAUI  
🎖️ VISUAL STUDIO VİDEOLARI ►    • Visual Studio  
🎉 BENCHMARKDOTNET VİDEOLARI ►    • BenchmarkDotNet  
✨ ALGORİTMA VİDEOLARI ►    • Algoritma  

🐦 Twitter'dan takip edin ►   / sonergonul  
💜 Twitch'ten takip edin ►   / sonergonul  
💚 Discord kanalımız ►   / discord  
💖 Quora'dan takip edin ► https://www.quora.com/profile/Soner-G...
💛 Instagram'dan takip edin ►   / sonergonul  
✨ Tiktok'tan takip edin ►  / soner_gonul  

💪 KATIL:    / soner gönül