Dijkstra'nın bir 2d dizisiyle algoritması

Question

Geçtiğimiz günlerde bu algoritmayı uygulamaya çalıştım. Şimdiye kadar dinamik bir 2d dizisi yapmayı ve düğümler arasındaki mesafeleri, düğümler arasındaki bir yolu ve iki düğüm arasında bir yol olup olmadığını söyleyen bir işlevi kaldırmayı başardım. Şimdi düğüm A'dan düğüme B en kısa yolunu döndüren bir işlev uygulamak istiyorum. Dijkstras algoritmasının nasıl çalıştığını biliyorum ve herhangi bir kodu kendim yazmadan wiki üzerindeki sözde kodu okudum. Gerçekten burada sıkıştım.

Kodun nasıl görünmesi gerektiğini ve nelerin olması gerektiğiyle ilgili olarak, iki düğüm arasında bir yol olup olmadığını söyleyen bu işlevi nasıl yaptığımı düşünüyorum. Dijkstra'ların uygulanmasını kolaylaştıracak başka yardım işlevlerine ihtiyacım var mı?

Şimdilik sadece 3 düğümüm var ama yazmak istediğim kodun genel olarak n düğümleri için çalışması gerekiyor.

Her türlü yardım için teşekkür ederiz.

Answer 1

Muhtemelen çok düşünürsünüz.

2 şey lazım. Anladığınız temiz bir grafik yapısı. Anladığınız algoritmanın iyi bir tanımı. Eğer ikisine de sahipseniz. Sadece bir kod yazmaya başla. İhtiyaç duyulan yardımcılar yolda belli olacak.

- düzenle -
Muhtemelen bağlantı için, Ill bunu bir görünüm vermek std::priority_queue

Answer 2

Bu algoritma için çeşitli kodlar buldum, ancak belki de daha iyi olması için en basit olanı daha iyidir, böylece sizinki ile bu arasındaki farkları kontrol edebilir ve sizinkileri tamamlayabilirsiniz. Yolunuzu programlamak her zaman daha iyidir.

Buna bir bakın ve yardımcı olup olmadığına bakın.

http://vinodcse.wordpress.com/2006/05/19/code-for-dijkstras-algorithm-in-c-2/

iyi şanslar.

Answer 3

Düzenleme: Kod silindi ve ben ipuçları vereceğim:

1. Mağaza grafiğini her köşe bitişik olması listelerinin listesi olarak. (bu gibi bir şey vector < vector < pair<int,int> > > g (n);)
2. Geçerli durumdaki minimum mesafeli vertex'i takip etmek için bazı veri yapılarını kullanın. (O(m log(n)) karmaşıklığına sahip olabilirsiniz veya priority_queue)
3. Her seferinde high_priority vertex'i (minimum akım mesafeli köşe) alın, bunu data_structure öğenizden silin ve bitişik bitişik olan bir köşeye kadar olan mesafeleri güncelleyin.

---

Not: size de asgari yolunu almak istiyorsanız tepe mesafesini güncellenirken, daha sonra (v diyelim) bazı vector<int> previous ve her defasında tutmakprevious[v] = index of vertex from where you came here ayarlayın. Yolunuz, ters sırayla last, prev[last], prev[prev[last]],...,first.