Jalur terpendek dengan shortestPath

Fungsi shortestPath bawaan dan kondisi kapan waktunya beralih ke GDS.

Daftar isi

Topik ini membahas pencarian jalur terpendek (shortest path) dengan fungsi bawaan Cypher, yaitu shortestPath() dan allShortestPaths(). Pertanyaan yang dijawabnya adalah rantai relasi sesingkat apa yang menghubungkan dua node tertentu. Pembahasan mencakup peran arah dan tipe relasi di dalam pola, penguraian jalur hasil dengan nodes() dan relationships(), serta kondisi yang menuntut perpindahan ke pustaka GDS. Seluruh contoh dieksekusi pada dataset modul ini, sehingga setiap keluaran dapat direproduksi ulang.

Dataset jaringan sosial#

Seluruh contoh pada modul ini menggunakan satu dataset kecil yang sama, yaitu jaringan sosial berisi tujuh node berlabel :Person dengan properti name dan kota, ditambah dua node :Hobi. Relasi :KENAL membentuk rantai Eko, Fajar, Gita, Hana, ditambah cabang Eko, Iwan, Hana, serta dua cabang pendek menuju Jihan dan Rara. Arah relasi diperlakukan bermakna, misalnya (Eko)-[:KENAL]->(Fajar) berarti Eko mengenal Fajar. Pasangan Eko dan Hana menjadi bahan utama topik ini karena dua rute berbeda menghubungkan keduanya. Rute pertama melewati Iwan, sedangkan rute kedua melewati Fajar dan Gita, sehingga panjangnya berbeda dan hanya satu yang terpendek.

Skrip setup.cypher berikut membangun seluruh dataset dengan MERGE, sehingga aman dijalankan berulang tanpa menduplikasi data. Isinya identik dengan skrip dataset pada topik lain di modul ini, sehingga hasil kueri antartopik dapat dibandingkan secara langsung. Cara termudah memuat skrip tersebut adalah mengalirkannya ke cypher-shell melalui pipa, atau mengeksekusinya dari Neo4j Browser. Kata sandi diminta interaktif agar tidak tersimpan di dalam riwayat perintah.

cypher setup.cypher

// Dataset modul Pola kueri: jaringan sosial dengan relasi KENAL dan hobi.
// Skrip ini idempoten, sehingga aman dijalankan lebih dari satu kali.

// Tujuh orang beserta kota asalnya
MERGE (p:Person {name: 'Eko'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Fajar'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Gita'}) SET p.kota = 'Semarang';
MERGE (p:Person {name: 'Hana'}) SET p.kota = 'Surabaya';
MERGE (p:Person {name: 'Iwan'}) SET p.kota = 'Semarang';
MERGE (p:Person {name: 'Jihan'}) SET p.kota = 'Bandung';
MERGE (p:Person {name: 'Rara'}) SET p.kota = 'Yogyakarta';

// Dua hobi
MERGE (h:Hobi {name: 'Fotografi'});
MERGE (h:Hobi {name: 'Bersepeda'});

// Rantai KENAL, kedua ujung diikat variabel agar MERGE hanya menangani relasinya
MATCH (a:Person {name: 'Eko'}), (b:Person {name: 'Fajar'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Person {name: 'Gita'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Gita'}), (b:Person {name: 'Hana'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Eko'}), (b:Person {name: 'Iwan'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Iwan'}), (b:Person {name: 'Hana'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Gita'}), (b:Person {name: 'Jihan'}) MERGE (a)-[:KENAL]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Person {name: 'Rara'}) MERGE (a)-[:KENAL]->(b);

// Hobi hanya dimiliki sebagian orang, sehingga null muncul secara alami
MATCH (a:Person {name: 'Hana'}), (b:Hobi {name: 'Fotografi'}) MERGE (a)-[:PUNYA_HOBI]->(b);
MATCH (a:Person {name: 'Fajar'}), (b:Hobi {name: 'Bersepeda'}) MERGE (a)-[:PUNYA_HOBI]->(b);

bash

# tidak-dijalankan
# memuat dataset melalui cypher-shell, kata sandi diminta interaktif
cypher-shell -a bolt://localhost:7687 -u neo4j -f setup.cypher

Fungsi shortestPath#

Fungsi shortestPath() menerima satu pola jalur dan mengembalikan satu jalur dengan jumlah relasi paling sedikit yang cocok dengan pola tersebut. Ukuran keterpendekannya adalah jumlah lompatan (hop), yaitu jumlah relasi yang dilalui, dan bukan jarak, bobot, atau properti apa pun. Pola di dalamnya ditulis seperti pola MATCH biasa, lengkap dengan label node, tipe relasi, arah, dan batas panjang, sehingga ruang pencarian dapat dipersempit sebelum kueri dieksekusi. Satu pembatasan perlu diingat, yaitu batas bawah pola hanya boleh bernilai nol atau satu, sedangkan batas atasnya bebas ditentukan.

Graf dataset memuat dua rute dari Eko menuju Hana. Kueri panjang variabel berikut mendaftar keduanya sebagai pembanding.

cypher

MATCH p = (a:Person {name: 'Eko'})-[:KENAL*2..3]->(b:Person {name: 'Hana'})
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang
ORDER BY panjang, rute;

text Keluaran

rute, panjang
["Eko", "Iwan", "Hana"], 2
["Eko", "Fajar", "Gita", "Hana"], 3

Rute melalui Iwan menempuh dua relasi, sedangkan rute melalui Fajar dan Gita menempuh tiga. Fungsi shortestPath() hanya mengambil yang terpendek.

cypher

MATCH p = shortestPath((a:Person {name: 'Eko'})-[:KENAL*]->(b:Person {name: 'Hana'}))
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang;

text Keluaran

rute, panjang
["Eko", "Iwan", "Hana"], 2

Keluarannya satu baris berisi jalur dua lompatan melalui Iwan, sedangkan rute tiga lompatan tidak pernah muncul dari fungsi ini. Apabila terdapat beberapa jalur yang sama pendek, salah satunya dikembalikan, dan dokumentasi resmi menyatakan jalur yang terpilih tidak deterministik karena bergantung pada urutan penelusuran internal.

Arah dan tipe relasi#

Arah relasi pada pola shortestPath() mengikuti panah yang ditulis, dan panah yang berlawanan dengan arah penyimpanan membuat pencarian gagal tanpa pesan error apa pun. Relasi :KENAL pada dataset tersimpan mengarah menjauhi Eko, sehingga pencarian terpendek dari Hana menuju Eko dengan pola berarah tidak menemukan jalur. Kueri berikut membungkus hasilnya dalam count(p) agar keluaran kosong terlihat sebagai angka nol.

cypher

MATCH p = shortestPath((a:Person {name: 'Hana'})-[:KENAL*]->(b:Person {name: 'Eko'}))
RETURN count(p) AS jumlah;

text Keluaran

jumlah
0

Nilai nol menegaskan bahwa tidak ada jalur berarah yang cocok, bukan bahwa Eko dan Hana tidak terhubung. Menghapus panah pada pola membuat relasi dicocokkan ke kedua arah, dan jalur terpendek langsung ditemukan kembali. Jalur yang muncul tetap dua lompatan melalui Iwan, karena penelusuran dua arah hanya memperluas ruang pencarian, bukan mengubah ukuran keterpendekannya.

cypher

MATCH p = shortestPath((a:Person {name: 'Hana'})-[:KENAL*]-(b:Person {name: 'Eko'}))
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang;

text Keluaran

rute, panjang
["Hana", "Iwan", "Eko"], 2

Tipe relasi bekerja sebagai penyaring kedua. Pola -[:KENAL*]- antara Hana dan node Bersepeda tidak menghasilkan apa pun karena node hobi hanya melekat pada relasi :PUNYA_HOBI. Menambahkan tipe tersebut menjadi -[:KENAL|PUNYA_HOBI*]- membuka jalur tiga lompatan berikut. Gabungan beberapa tipe ditulis di dalam kurung siku dengan pemisah garis vertikal.

cypher

MATCH p = shortestPath((a:Person {name: 'Hana'})-[:KENAL|PUNYA_HOBI*]-(b:Hobi {name: 'Bersepeda'}))
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang;

text Keluaran

rute, panjang
["Hana", "Gita", "Fajar", "Bersepeda"], 3

Semua jalur terpendek dengan allShortestPaths#

Fungsi allShortestPaths() mengembalikan seluruh jalur yang berpanjang minimal sama untuk sebuah pola, bukan satu jalur saja. Bentuk polanya sama seperti shortestPath(), begitu pula ukuran keterpendekannya, yaitu jumlah lompatan. Pada pasangan Eko dan Hana, hanya rute melalui Iwan yang berpanjang minimal, sehingga keluarannya tetap satu baris dan rute tiga lompatan tetap tidak disertakan.

cypher

MATCH p = allShortestPaths((a:Person {name: 'Eko'})-[:KENAL*]-(b:Person {name: 'Hana'}))
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang
ORDER BY panjang, rute;

text Keluaran

rute, panjang
["Eko", "Iwan", "Hana"], 2

Apabila dua jalur atau lebih sama-sama berpanjang minimal, seluruhnya muncul sebagai baris tersendiri, dan ORDER BY menjaga urutannya tetap deterministik. Kebutuhan lain adalah mengambil sejumlah k jalur terpendek tanpa menuntut sama panjang. Kebutuhan itu dilayani kata kunci SHORTEST k pada pola jalur terkuantifikasi (quantified path pattern), dengan angka pada SHORTEST 2 berarti banyaknya jalur yang diminta, bukan panjangnya. Kueri berikut mengambil dua jalur terpendek antara Eko dan Hana sehingga kedua rute muncul berdampingan.

cypher

MATCH p = SHORTEST 2 (a:Person {name: 'Eko'})-[:KENAL]-+(b:Person {name: 'Hana'})
RETURN [n IN nodes(p) | n.name] AS rute, length(p) AS panjang
ORDER BY panjang, rute;

text Keluaran

rute, panjang
["Eko", "Iwan", "Hana"], 2
["Eko", "Fajar", "Gita", "Hana"], 3

Membedah jalur dengan nodes() dan relationships()#

Jalur yang dikembalikan berupa objek jalur (path) yang dapat diurai menjadi daftar node dan daftar relasi. Fungsi nodes() mengembalikan seluruh node sesuai urutan kunjungannya, sedangkan relationships() mengembalikan relasi-relasinya. Fungsi type() mengambil tipe setiap relasi, dan length(p) senilai dengan size(relationships(p)) karena keduanya menghitung jumlah relasi. Kueri berikut mengurai jalur terpendek antara Jihan dan Rara, yang menempuh tiga relasi melalui Gita dan Fajar.

cypher

MATCH p = shortestPath((a:Person {name: 'Jihan'})-[:KENAL*]-(b:Person {name: 'Rara'}))
RETURN [n IN nodes(p) | n.name] AS orang, [r IN relationships(p) | type(r)] AS tipe_relasi, length(p) AS panjang;

text Keluaran

orang, tipe_relasi, panjang
["Jihan", "Gita", "Fajar", "Rara"], ["KENAL", "KENAL", "KENAL"], 3

Kolom orang memuat urutan node dari ujung ke ujung, sedangkan kolom tipe_relasi memuat tipe setiap relasi yang dilalui. Panjang pada kolom ketiga selalu senilai dengan banyaknya anggota tipe_relasi karena setiap relasi membawa tepat satu tipe. Proyeksi berupa list juga lebih mudah dibaca daripada nilai jalur mentah, karena nilai mentah menampilkan seluruh properti node di dalamnya. Penguraian semacam ini diperlukan ketika isi jalur diproses lebih lanjut, misalnya menyaring node tertentu atau mengumpulkan properti di sepanjang lintasan, dan teknik daftarnya berkaitan erat dengan pengolahan list yang dibahas pada topik tersendiri dalam modul ini.

Kapan beralih ke GDS#

Fungsi bawaan cukup selama graf masih kecil, kueri masih berupa pencarian titik ke titik, dan ukuran keterpendekan yang dibutuhkan memang jumlah lompatan. Begitu terdekat berarti jarak, waktu tempuh, atau biaya yang tersimpan sebagai properti relasi, shortestPath() tidak lagi memadai karena perhitungannya murni menghitung lompatan. Pustaka Neo4j Graph Data Science (GDS) menyediakan algoritma jalur berbobot seperti Dijkstra, A*, dan Yen yang dikerjakan pada proyeksi graf, sebagaimana dibahas pada modul Algoritma graf dengan GDS.

Dokumentasi Cypher merangkum pembagian peran tersebut. Cypher dipilih untuk navigasi pola yang kompleks, graf yang kecil, atau keadaan ketika proyeksi GDS tidak tersedia, sedangkan GDS dipilih untuk jalur berbobot, algoritma khusus, dan analitik yang melibatkan banyak pasangan node sekaligus. Aturan praktisnya, pertanyaan operasional atas satu pasangan node dilayani Cypher, sedangkan pertanyaan analitik berat dilayani GDS.

Kesalahan umum#

Kesalahan pertama adalah menganggap shortestPath() mengembalikan seluruh rute yang tersedia. Fungsinya mengembalikan satu jalur saja, dan rute yang lebih panjang, sekalipun sah, tidak pernah muncul di dalam hasilnya. Perbaikannya adalah memilih fungsi sesuai kebutuhan, yaitu allShortestPaths() untuk seluruh jalur berpanjang minimal dan SHORTEST k untuk sejumlah k jalur terpendek.

Kesalahan kedua adalah menulis batas bawah lebih dari satu pada pola di dalam shortestPath(), misalnya *3..3. Eksekusinya gagal dengan error invalid lower bound karena fungsi ini hanya menerima batas bawah 0 atau 1. Jalur terpendek di antara kandidat berpanjang tertentu dicari dengan pola panjang variabel biasa yang diurutkan menurut length(p) lalu dibatasi LIMIT 1.

Kesalahan ketiga adalah membaca keluaran kosong sebagai bukti bahwa dua node tidak terhubung. Pola berarah yang panahnya berlawanan dengan arah penyimpanan mengembalikan hasil kosong, sebagaimana pencarian Hana menuju Eko pada bagian sebelumnya. Perbaikannya adalah memeriksa arah relasi yang tersimpan, menghapus panah dari pola, atau menambahkan tipe relasi yang relevan.

Ringkasan#

shortestPath() mengembalikan satu jalur dengan jumlah lompatan tersedikit, dan di antara jalur yang sama pendek jalur terpilihnya tidak deterministik.
Arah dan tipe relasi pada pola berperan sebagai penyaring, sehingga pola berarah yang salah arah menghasilkan keluaran kosong.
allShortestPaths() mengembalikan seluruh jalur yang berpanjang minimal, sedangkan SHORTEST k mengembalikan k jalur terpendek tanpa menuntut sama panjang.
Fungsi nodes() dan relationships() mengurai jalur menjadi daftar node dan relasi, sedangkan jalur berbobot dilayani algoritma GDS seperti Dijkstra.

Referensi#

Shortest paths — Neo4j Docs — Semantik kata kunci SHORTEST, kedudukan fungsi shortestPath dan allShortestPaths, serta panduan memilih antara Cypher dan GDS.
Dijkstra Source-Target Shortest Path — Neo4j Docs — Algoritma jalur berbobot pada pustaka GDS yang menggunakan properti biaya relasi.