Implementation (Part 2)
Coddy'nin Dijkstra Algoritması - Graf Algoritmaları kursunda ders 6 / 9.
Şimdi açgözlü (greedy) en kısa yol hesaplaması.
Görev
OrtaŞimdi algoritmanın tamamını oluşturun.
n, düz edges dizisi (üçlüler, yönlendirilmiş, negatif olmayan ağırlıklar) ve bir source alan ve v konumunun source'dan v'ye olan en kısa mesafe olduğu bir dizi döndüren dijkstra adında bir fonksiyon yazın. Ulaşılamayan düğümler için -1 kullanın.
Kaynak 0 hariç tüm mesafeleri büyük bir "sonsuz" değerle başlatın. Ardından, n kez, en yakın ziyaret edilmemiş düğümü kesinleştirin ve onun dışa giden kenarlarını gevşetin (relax).
Kendin dene
#include <stdlib.h>
int* dijkstra(int n, int* edges, int edges_size, int source, int* returnSize) {
// Kodu buraya yazın
*returnSize = 0;
return edges;
}
Kendini test etBu ders kısa bir quiz içerir. Soruları yanıtlamak ve ilerlemeni kaydetmek için derse başla.
Dijkstra Algoritması - Graf Algoritmaları bölümündeki tüm dersler
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity