Pencarian Jalur

Dijkstra pada graf berbobot untuk persoalan jangkauan, dengan rujukan silang ke teori DSA.

Daftar isi

Topik ini membahas tiga algoritma pencarian jalur pada pustaka GDS, yaitu Dijkstra untuk jarak terpendek berbobot, A* untuk pencarian yang dipandu koordinat, dan Yen untuk k jalur terpendek alternatif. Ketiganya dijalankan dalam mode stream atas jaringan transportasi modul ini dengan pola kerja tiga langkah yang diperkenalkan pada topik Pustaka GDS, yaitu memproyeksikan graf, menjalankan algoritma, lalu menyingkirkan proyeksinya. Teori BFS, DFS, dan Dijkstra menjadi bagian materi algoritma dan struktur data, sehingga teori tersebut digunakan langsung di sini tanpa dibuktikan ulang. Setelah topik ini dibaca, ketiga prosedur dapat dijalankan pada dataset yang sama dan algoritma yang sesuai dapat dipilih untuk persoalan jangkauan maupun aliran.

Dijkstra untuk jarak terpendek berbobot#

Dijkstra mencari jalur dengan total bobot terkecil antara satu node asal dan satu node tujuan. Algoritma ini mengunjungi node secara menaik menurut biaya kumulatif dari asal, sehingga ketika tujuan tercapai, biayanya dijamin minimum. Pada GDS, Dijkstra dijalankan melalui prosedur gds.shortestPath.dijkstra.stream atas proyeksi yang membawa bobot relasi. Dataset modul menyimpan jarak pada properti jarak, sehingga bobot yang dioptimalkan adalah kilometer dan bukan jumlah pemberhentian yang dilalui.

Contoh dijalankan atas dataset jaringan transportasi modul yang dimuat dari berkas setup.cypher berikut. Isinya sama dengan berkas setup.cypher pada topik Pustaka GDS dan aman dijalankan berulang kali.

cypher setup.cypher

// Dataset contoh modul Algoritma graf dengan GDS: jaringan transportasi mini
// dengan delapan pemberhentian dan relasi KE berbobot jarak.
// Skrip ini idempoten (idempotent), artinya aman dijalankan berulang kali.

// Node pemberhentian: label :Pemberhentian dengan properti name.
MERGE (:Pemberhentian {name: "Mangga"});
MERGE (:Pemberhentian {name: "Melati"});
MERGE (:Pemberhentian {name: "Cemara"});
MERGE (:Pemberhentian {name: "Kenanga"});
MERGE (:Pemberhentian {name: "Cempaka"});
MERGE (:Pemberhentian {name: "Anggrek"});
MERGE (:Pemberhentian {name: "Flamboyan"});
MERGE (:Pemberhentian {name: "Bougenvil"});

// Relasi KE berarah antar pemberhentian, dengan properti jarak dalam kilometer.
MATCH (a:Pemberhentian {name: "Mangga"}), (b:Pemberhentian {name: "Melati"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 3;
MATCH (a:Pemberhentian {name: "Melati"}), (b:Pemberhentian {name: "Cemara"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Cemara"}), (b:Pemberhentian {name: "Kenanga"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 4;
MATCH (a:Pemberhentian {name: "Kenanga"}), (b:Pemberhentian {name: "Cempaka"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Cempaka"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 5;
MATCH (a:Pemberhentian {name: "Anggrek"}), (b:Pemberhentian {name: "Flamboyan"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 3;
MATCH (a:Pemberhentian {name: "Flamboyan"}), (b:Pemberhentian {name: "Bougenvil"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 2;
MATCH (a:Pemberhentian {name: "Bougenvil"}), (b:Pemberhentian {name: "Mangga"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 4;
MATCH (a:Pemberhentian {name: "Melati"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 6;
MATCH (a:Pemberhentian {name: "Cemara"}), (b:Pemberhentian {name: "Anggrek"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 9;
MATCH (a:Pemberhentian {name: "Kenanga"}), (b:Pemberhentian {name: "Bougenvil"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 7;
MATCH (a:Pemberhentian {name: "Cempaka"}), (b:Pemberhentian {name: "Melati"})
  MERGE (a)-[r:KE]->(b)
  SET r.jarak = 8;

bash

# tidak-dijalankan
# memuat ulang dataset contoh modul sebelum contoh dijalankan
cat setup.cypher | cypher-shell -u neo4j

Kueri berikut mencari jalur termurah dari Mangga ke Anggrek. Proyeksi bernama jalur-dijkstra-m7 dibuat dengan properti relasi jarak, algoritma dijalankan atas nama proyeksi tersebut, dan proyeksinya langsung disingkirkan.

cypher

CALL gds.graph.project(
  'jalur-dijkstra-m7',
  'Pemberhentian',
  'KE',
  {relationshipProperties: 'jarak'}
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

text Keluaran

graphName, nodeCount, relationshipCount
"jalur-dijkstra-m7", 8, 12

cypher

MATCH (asal:Pemberhentian {name: "Mangga"}), (tujuan:Pemberhentian {name: "Anggrek"})
CALL gds.shortestPath.dijkstra.stream('jalur-dijkstra-m7', {
  sourceNode: asal,
  targetNode: tujuan,
  relationshipWeightProperty: 'jarak'
})
YIELD totalCost, nodeIds, costs
RETURN totalCost AS totalJarak,
       [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS rute,
       costs AS kumulatif;

text Keluaran

totalJarak, rute, kumulatif
9.0, ["Mangga", "Melati", "Anggrek"], [0.0, 3.0, 9.0]

cypher

CALL gds.graph.drop('jalur-dijkstra-m7')
YIELD graphName
RETURN graphName;

text Keluaran

graphName
"jalur-dijkstra-m7"

Keluaran di atas melaporkan total jarak 9.0 kilometer melalui rute Mangga, Melati, dan Anggrek, yang memanfaatkan jalur pintas Melati menuju Anggrek sepanjang enam kilometer. Daftar kumulatif menyatakan biaya dari asal menuju setiap node pada rute, yaitu 0.0 di titik asal, 3.0 di Melati, dan 9.0 di tujuan. Pola tiga langkah yang sama digunakan dua algoritma berikutnya dengan nama proyeksi yang berbeda, sehingga uraian pada bagian berikutnya hanya menyoroti konfigurasi yang berubah.

A* dengan koordinat pemberhentian#

A* adalah perluasan Dijkstra yang memandu pencarian dengan heuristik, yakni perkiraan biaya dari sebuah node menuju tujuan. GDS menghitung perkiraan itu dengan rumus haversine, yaitu jarak dua titik pada permukaan bola, atas dua properti koordinat node. Arah pencarian menjadi condong ke tujuan sehingga tidak semua sisi graf perlu dijelajahi, dan manfaatnya semakin nyata pada graf berukuran besar.

Koordinat pada dataset modul perlu ditetapkan lebih dahulu karena pemberhentian hanya menyimpan nama. Kueri berikut menetapkan properti lintang dan bujur kedelapan pemberhentian dalam satu kueri dan mengembalikan isinya sebagai konfirmasi.

cypher

UNWIND [
  {nama: "Mangga",    lintang: -6.211, bujur: 106.811},
  {nama: "Melati",    lintang: -6.214, bujur: 106.816},
  {nama: "Cemara",    lintang: -6.219, bujur: 106.819},
  {nama: "Kenanga",   lintang: -6.224, bujur: 106.817},
  {nama: "Cempaka",   lintang: -6.227, bujur: 106.812},
  {nama: "Anggrek",   lintang: -6.225, bujur: 106.806},
  {nama: "Flamboyan", lintang: -6.219, bujur: 106.802},
  {nama: "Bougenvil", lintang: -6.214, bujur: 106.805}
] AS baris
MATCH (p:Pemberhentian {name: baris.nama})
SET p.lintang = baris.lintang, p.bujur = baris.bujur
RETURN p.name AS nama, p.lintang AS lintang, p.bujur AS bujur ORDER BY nama;

text Keluaran

nama, lintang, bujur
"Anggrek", -6.225, 106.806
"Bougenvil", -6.214, 106.805
"Cemara", -6.219, 106.819
"Cempaka", -6.227, 106.812
"Flamboyan", -6.219, 106.802
"Kenanga", -6.224, 106.817
"Mangga", -6.211, 106.811
"Melati", -6.214, 106.816

Nilai koordinat dipilih agar jarak garis lurus antar pemberhentian selalu di bawah dua kilometer, sedangkan bobot jarak paling kecil dua kilometer. Kondisi ini menjaga heuristik tetap admissible, yaitu tidak pernah melebihi biaya sebenarnya menuju tujuan, sehingga jalur yang dikembalikan tetap optimal.

Proyeksi untuk A* menambahkan nodeProperties berisi kedua koordinat, sedangkan bobot relasinya tetap jarak. Konfigurasi algoritma menyebut nama lintang dan bujur melalui latitudeProperty serta longitudeProperty.

cypher

CALL gds.graph.project(
  'jalur-astar-m7',
  'Pemberhentian',
  'KE',
  {nodeProperties: ['lintang', 'bujur'], relationshipProperties: 'jarak'}
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

text Keluaran

graphName, nodeCount, relationshipCount
"jalur-astar-m7", 8, 12

cypher

MATCH (asal:Pemberhentian {name: "Mangga"}), (tujuan:Pemberhentian {name: "Cempaka"})
CALL gds.shortestPath.astar.stream('jalur-astar-m7', {
  sourceNode: asal,
  targetNode: tujuan,
  latitudeProperty: 'lintang',
  longitudeProperty: 'bujur',
  relationshipWeightProperty: 'jarak'
})
YIELD totalCost, nodeIds, costs
RETURN totalCost AS totalJarak,
       [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS rute,
       costs AS kumulatif;

text Keluaran

totalJarak, rute, kumulatif
11.0, ["Mangga", "Melati", "Cemara", "Kenanga", "Cempaka"], [0.0, 3.0, 5.0, 9.0, 11.0]

cypher

CALL gds.graph.drop('jalur-astar-m7')
YIELD graphName
RETURN graphName;

text Keluaran

graphName
"jalur-astar-m7"

Hasilnya adalah rute Mangga, Melati, Cemara, Kenanga, dan Cempaka dengan total 11.0 kilometer. Heuristik haversine pada contoh ini hanya mempersempit wilayah pencarian tanpa mengubah biaya rute yang dilaporkan, sebab perkiraannya selalu lebih kecil daripada bobot relasi sebenarnya. Pada graf yang jauh lebih besar, heuristik inilah yang menghemat jumlah node yang dikunjungi.

Yen untuk beberapa jalur alternatif#

Dijkstra dan A* mengembalikan tepat satu jalur, sedangkan banyak persoalan memerlukan beberapa pilihan, misalnya rute cadangan ketika rute utama padat atau analisis keragaman rute pada jaringan. Algoritma Yen menghasilkan k jalur terpendek yang tidak melewati node yang sama dua kali, diurutkan menaik menurut total biayanya. Dari segi mekanisme, Yen menjalankan pencarian Dijkstra berulang kali pada graf yang dimodifikasi di sekitar jalur yang sudah ditemukan, sehingga setiap putaran menghasilkan satu jalur baru.

Banyaknya jalur yang diminta ditetapkan melalui konfigurasi k. Contoh berikut meminta tiga jalur alternatif dari Mangga ke Bougenvil atas proyeksi jalur-yens-m7.

cypher

CALL gds.graph.project(
  'jalur-yens-m7',
  'Pemberhentian',
  'KE',
  {relationshipProperties: 'jarak'}
)
YIELD graphName, nodeCount, relationshipCount
RETURN graphName, nodeCount, relationshipCount;

text Keluaran

graphName, nodeCount, relationshipCount
"jalur-yens-m7", 8, 12

cypher

MATCH (asal:Pemberhentian {name: "Mangga"}), (tujuan:Pemberhentian {name: "Bougenvil"})
CALL gds.shortestPath.yens.stream('jalur-yens-m7', {
  sourceNode: asal,
  targetNode: tujuan,
  k: 3,
  relationshipWeightProperty: 'jarak'
})
YIELD index, totalCost, nodeIds
RETURN index, totalCost AS totalJarak,
       [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS rute
ORDER BY totalJarak ASC, index ASC;

text Keluaran

index, totalJarak, rute
0, 14.0, ["Mangga", "Melati", "Anggrek", "Flamboyan", "Bougenvil"]
1, 16.0, ["Mangga", "Melati", "Cemara", "Kenanga", "Bougenvil"]
2, 19.0, ["Mangga", "Melati", "Cemara", "Anggrek", "Flamboyan", "Bougenvil"]

cypher

CALL gds.graph.drop('jalur-yens-m7')
YIELD graphName
RETURN graphName;

text Keluaran

graphName
"jalur-yens-m7"

Ketiga jalur berbiaya 14.0, 16.0, dan 19.0 kilometer dengan segmen tengah yang berbeda, dan urutan pertamanya adalah jalur termurah untuk pasangan tersebut. Apabila k lebih besar daripada jumlah jalur yang tersedia, prosedur mengembalikan sebanyak jalur yang dapat ditemukan tanpa menimbulkan error. Pada dataset ini, permintaan sepuluh jalur menghasilkan empat jalur karena jumlah jalur tanpa perulangan node dari Mangga ke Bougenvil memang hanya empat.

Penutup siklus kerjanya adalah pemeriksaan katalog. Prosedur gds.graph.list() tanpa argumen mengembalikan daftar proyeksi yang masih terpasang, dan hitungan berikut bernilai nol karena ketiga proyeksi sudah disingkirkan satu per satu.

cypher

CALL gds.graph.list()
YIELD graphName
RETURN count(graphName) AS jumlahProyeksi;

text Keluaran

jumlahProyeksi
0

Memilih algoritma yang sesuai#

Ketiga algoritma menjawab pertanyaan yang sedikit berbeda, sehingga pilihannya ditentukan oleh masukan yang tersedia dan bentuk hasil yang dibutuhkan. Tabel berikut merangkum perbandingannya.

Algoritma	Masukan tambahan	Hasil	Cocok untuk
Dijkstra	bobot relasi	satu jalur termurah	jangkauan umum tanpa koordinat
A*	bobot relasi dan koordinat node	satu jalur termurah	graf besar dengan koordinat tersedia
Yen	bobot relasi dan nilai `k`	beberapa jalur alternatif	rute cadangan dan penyusun analisis aliran

Dijkstra menuntut masukan paling sedikit karena hanya memerlukan bobot relasi, sehingga menjadi pilihan pertama apabila koordinat tidak tersedia dan satu jalur sudah cukup. A* memberikan hasil yang sama dengan Dijkstra sepanjang heuristiknya admissible, sedangkan keunggulannya terletak pada pencarian yang lebih terarah pada graf berukuran besar. Yen dipilih apabila satu jalur saja tidak menjawab persoalannya, misalnya menyediakan alternatif rute atau mengumpulkan banyak jalur pendek sekaligus.

Pemilihan algoritma juga mengikuti bentuk persoalannya. Persoalan jangkauan biasanya berhenti pada jalur termurah antara dua titik, sedangkan persoalan aliran seperti aliran maksimum menggunakan jalur-jalur pendek sebagai bahan penyusunnya. Ketiga prosedur pada topik ini bekerja dalam mode stream, sehingga rute yang dikembalikan berupa baris kueri dan dapat langsung diolah lebih lanjut oleh kueri yang sama.

Kesalahan umum#

Tiga kesalahan berikut paling sering muncul saat topik ini dipraktikkan.

Konfigurasi relationshipWeightProperty tidak disertakan pada pemanggilan algoritma. Pencarian tetap berjalan, tetapi setiap relasi dihitung berbobot 1.0 sehingga hasilnya adalah jalur dengan relasi paling sedikit dan bukan jarak termurah. Angka semacam ini sulit dikenali sebagai kesalahan karena nilainya terlihat wajar. Perbaikannya adalah menyertakan konfigurasi tersebut dan memastikan properti bobot ikut diproyeksikan melalui relationshipProperties.
Proyeksi A* tidak membawa properti koordinat. Prosedur menolak dijalankan dengan pesan error bahwa properti seperti lintang belum dimuat. Perbaikannya adalah menetapkan koordinat node terlebih dahulu apabila belum ada, menambahkannya pada nodeProperties saat gds.graph.project, lalu menyamakan nama propertinya pada latitudeProperty serta longitudeProperty.
Arah relasi diabaikan. Relasi KE berarah, sehingga biaya dari Mangga ke Cempaka berbeda dengan biaya perjalanan baliknya karena sisi lingkar yang dilalui berbeda. Pasangan yang tidak terhubung searah menghasilkan baris kosong tanpa pesan error apa pun. Perbaikannya adalah memeriksa arah relasi dengan MATCH, atau memproyeksikan ulang graf dengan orientasi UNDIRECTED apabila jalur dua arah memang diinginkan.

Ringkasan#

gds.shortestPath.dijkstra.stream menghitung satu jalur termurah atas bobot relasi yang dibawa proyeksi melalui relationshipProperties, dan konfigurasi relationshipWeightProperty yang tertinggal mengubah hasilnya menjadi hitungan relasi.
gds.shortestPath.astar.stream memandu pencarian dengan heuristik haversine atas properti koordinat node yang wajib disertakan pada nodeProperties proyeksi.
gds.shortestPath.yens.stream mengembalikan k jalur alternatif tanpa perulangan node, diurutkan menaik menurut total biaya.
Setiap algoritma dijalankan atas proyeksinya sendiri dengan pola gds.graph.project, eksekusi mode stream, lalu gds.graph.drop, sehingga katalog proyeksi milik topik ini kembali kosong.

Referensi#

Dijkstra Single-Source Shortest Path — Neo4j Docs — Konfigurasi sourceNode, targetNode, dan relationshipWeightProperty pada prosedur Dijkstra beserta mode eksekusinya.
A* Shortest Path — Neo4j Docs — Heuristik haversine, konfigurasi latitudeProperty dan longitudeProperty, serta syarat heuristik admissible.
Yen’s Shortest Path algorithm — Neo4j Docs — Prosedur Yen untuk k jalur terpendek beserta konfigurasi k dan mode stream.