Mencari Rute Terdekat Menggunakan Metode Graf - CRUDPRO
Home  ›  Others

Mencari Rute Terdekat Menggunakan Metode Graf

Written By Wednesday, September 21, 2022
Mencari Rute Terdekat Menggunakan Metode Graf

Ketika datang untuk menemukan jalur terpendek dalam grafik, kebanyakan orang memikirkan algoritma Dijkstra (juga disebut algoritma Jalur Terpendek Pertama Dijkstra). Sementara algoritma Dijkstra memang sangat berguna, ada pendekatan sederhana yang dapat digunakan berdasarkan sifat-sifat grafik. Ini bisa sangat berguna dalam kontes pemrograman kompetitif atau wawancara pengkodean, di mana Anda mungkin dipaksa untuk membuat kode algoritma jalur terpendek dengan tangan. Anda memerlukan pendekatan sesederhana mungkin untuk mengurangi kemungkinan bug dalam kode Anda.

Jika Anda tidak terbiasa dengan grafik atau pencarian mendalam-pertama (DFS) dan pencarian luas-pertama (BFS), saya sarankan membaca bagian ini.

Untuk algoritme berikut, kami akan menganggap bahwa grafik disimpan dalam daftar ketetanggaan dengan bentuk berikut:

1. const adjacencyList = new Map();
2. adjacencyList.set(NODE_ID, new Set([...]));

Ini adalah HashMap dari HashSets dan menyimpan node yang berdekatan untuk setiap node.

Selanjutnya, setiap algoritma akan mengembalikan jarak terpendek antara dua node serta peta yang kita sebut sebelumnya. Peta itu menyimpan pendahulu dari setiap simpul yang ada di jalur terpendek. Dengan pemetaan ini, kita dapat mencetak node pada jalur terpendek sebagai berikut:

const printPath = (previous, startNode, stopNode) => {
  let currentNode = stopNode;
  console.log(currentNode);
  while (currentNode !== startNode) {
    currentNode = previous.get(currentNode);
    console.log(currentNode);
  }
}

1. Pencarian Depth-First (DFS)

Ini mungkin algoritma paling sederhana untuk mendapatkan jalur terpendek. Namun, ada juga kekurangannya. Grafik Anda harus berupa pohon atau polytree. Jika kondisi ini terpenuhi, Anda dapat menggunakan DFS yang sedikit dimodifikasi untuk menemukan jalur terpendek Anda:

1. const shortestPathDfs = (startNode, stopNode) => {
2. 	const previous = new Map();
3. 	let shortestDistance = -1;
4. 	const dfs = (currentNode, depth) => {
5.  	if (currentNode === stopNode) {
6.	      shortestDistance = depth;
7.    } else {
8.      for (let neighbour of adjacencyList.get(currentNode)) {
9.        previous.set(neighbour, currentNode);
10.        dfs(neighbour, depth + 1);
11.      }
12.    }
13.  };
14.  dfs(startNode, 0);
15.  return { shortestDistance, previous };
16. };

Jika tidak ada jalur antara startNode dan stopNode, jalur terpendek akan memiliki panjang -1. Kami menginisialisasi jalur terpendek dengan nilai ini dan memulai DFS rekursif. DFS rekursif itu sedikit dimodifikasi dalam arti bahwa ia akan melacak kedalaman pencarian dan berhenti segera setelah mencapai stopNode. Kedalaman saat ini ketika mencapai stopNode adalah panjang jalur terpendek kami.

Alasan mengapa kami tidak dapat menggunakannya untuk grafik siklik adalah karena setiap kali kami menemukan jalur, kami tidak dapat memastikan bahwa itu adalah jalur terpendek. DFS tidak memberikan jaminan seperti itu.

Pertunjukan

Biarkan n menjadi jumlah node dan e menjadi jumlah tepi dalam grafik kami. Algoritma ini kemudian memiliki kompleksitas waktu O(n). Karena sifatnya yang rekursif, ia menggunakan tumpukan panggilan dan oleh karena itu memiliki konsumsi memori asimtotik sebesar O(n).

Mengapa tidak O(n + e)? Nah, ini karena kami berasumsi bahwa grafik kami adalah asiklik. Ini berarti bahwa e n-1 dan oleh karena itu O(n+e) = O(n).

2. Pencarian Breadth-First (BFS)

BFS yang sedikit dimodifikasi adalah algoritma yang sangat berguna untuk menemukan jalur terpendek. Ini sederhana dan berlaku untuk semua grafik tanpa bobot tepi:

1. const shortestPathBfs = (startNode, stopNode) => {
2.  const previous = new Map();
3.  const visited = new Set();
4.  const queue = [];
5.  queue.push({ node: startNode, dist: 0 });
6.  visited.add(startNode);
7. 
8.	while (queue.length > 0) {
9.   const { node, dist } = queue.shift();
10.    if (node === stopNode) 
11.		return { shortestDistande: dist, previous };
12.
13.    for (let neighbour of adjacencyList.get(node)) {
14.      if (!visited.has(neighbour)) {
15.        previous.set(neighbour, node);
16.        queue.push({ node: neighbour, dist: dist + 1 });
17.        visited.add(neighbour);
18.      }
19.    }
20.  }
21.  return { shortestDistance: -1, previous };
22. };

Ini adalah implementasi langsung dari BFS yang hanya berbeda dalam beberapa detail. Dengan setiap node yang disimpan dalam antrian, kami juga menghemat jarak ke startNode. Ketika kami mencapai stopNode, kami hanya mengembalikan jarak yang disimpan bersamanya.

Ini berfungsi karena sifat BFS: Tetangga tetangga tidak dikunjungi sebelum semua tetangga langsung dikunjungi. Akibatnya, semua node dengan jarak x dari startNode dikunjungi setelah semua node dengan jarak < x telah dikunjungi. BFS pertama-tama akan mengunjungi node dengan jarak 0 kemudian semua node dengan jarak 1 dan seterusnya. Properti ini adalah alasan mengapa kita dapat menggunakan BFS untuk menemukan jalur terpendek bahkan dalam grafik siklik.

Pertunjukan

Biarkan g menggambarkan jumlah terbesar dari node yang berdekatan untuk setiap node dalam grafik kami. Selain itu, misalkan d adalah panjang jalur terpendek antara startNode dan stopNode. Maka algoritma ini memiliki kompleksitas waktu O(gᵈ).

Mengapa demikian? Sebuah BFS mencari grafik di tingkat yang disebut. Setiap node dalam sebuah level memiliki jarak yang sama ke node awal. Dibutuhkan O(g) langkah untuk mencapai level 1, O(g²) langkah untuk mencapai level 2, dan seterusnya. Oleh karena itu, dibutuhkan langkah O(gᵈ) untuk mencapai level d. Menggunakan variabel n dan e lagi, runtime masih O(n + e). Namun, O(gᵈ) adalah pernyataan yang lebih tepat jika mencari jalur terpendek.

Dalam beberapa grafik, antrian dapat berisi semua node-nya. Oleh karena itu, ia juga memiliki kompleksitas ruang O(n).

Sebuah komentar kecil: Runtime aktual dari implementasi di atas lebih buruk daripada O(n + e). Alasannya adalah bahwa array JavaScript digunakan sebagai antrian. Operasi shift membutuhkan waktu O(s), di mana s adalah ukuran antrian. Namun, adalah mungkin untuk mengimplementasikan antrian dalam JavaScript yang memungkinkan operasi enqueue dan dequeue di O(1), seperti yang dijelaskan di bagian saya sebelumnya.

3. Pencarian Dua Arah

Metode ketiga kami untuk mendapatkan jalur terpendek adalah pencarian dua arah. Seperti BFS, ini berlaku untuk graf tak berarah tanpa bobot sisi. Untuk melakukan pencarian dua arah, pada dasarnya kita memulai satu BFS dari node1 dan satu dari node2 secara bersamaan. Ketika kedua BFS bertemu, kami telah menemukan jalur terpendek.

1. const addIfUnset = (map, key, value) => {
2.  if (!map.has(key)) {
3.    map.set(key, value);
4.  }
5. }
6.
7. const shortestPathBfs = (adjList, queue, visitedOwn, visitedOther, previous, isBackwards) => {
8.	  if (queue.length > 0) {
9.    const { node, dist } = queue.shift();
10.    if (visitedOther.has(node)) {
11.      return {
12.        shortestDistance: dist + visitedOther.get(node),
13.        previous,
14.      };
15.    }
16.
17.    for (let neighbour of adjList.get(node)) {
18.      if (!visitedOwn.has(neighbour)) {
19.        if (isBackwards) {
20.          addIfUnset(previous, node, neighbour);
21.        } else {
22.          addIfUnset(previous, neighbour, node);
23.        }
24.        queue.push({ node: neighbour, dist: dist + 1 });
25.        visitedOwn.set(neighbour, dist + 1);
26      }
27.    }
28.  }
29. };
30.
31. const bidirectionalSearch = (adjList, startNode, stopNode) => {
32.  const previous = new Map();
33.  const visited1 = new Map();
34.  const visited2 = new Map();
35.  const queue1 = [];
36.  const queue2 = [];
37.  queue1.push({ node: startNode, dist: 0 });
38.  queue2.push({ node: stopNode, dist: 0 });
39.  visited1.set(startNode, 0);
40.  visited2.set(stopNode, 0);
41.
42.  while (queue1.length > 0 || queue2.length > 0) {
43.    shortestPathBfs(adjList, queue1, visited1, visited2, previous, false);
44.    shortestPathBfs(adjList, queue2, visited2, visited1, previous, true);
45.  }
47.  return { shortestDistance: -1, previous };
48. };

Ini bukan algoritma terpendek, tetapi masih sederhana dan mudah dikodekan dari awal jika Anda tahu BFS. Tapi apa kelebihannya dibandingkan BFS biasa, yang jauh lebih pendek? Jawabannya adalah kinerja. Jika BFS memungkinkan kita menemukan jalur dengan panjang l dalam waktu yang wajar, pencarian dua arah akan memungkinkan kita menemukan jalur dengan panjang 2l.

Performa lebih detail: Pencarian dua arah berakhir setelah d/2 level karena ini adalah pusat jalur. Kedua BFS secara bersamaan mengunjungi masing-masing node g^(d/2), yaitu total 2g^(d/2). Ini mengarah ke O(g^(d/2)) dan oleh karena itu membuat pencarian dua arah lebih cepat daripada BFS dengan faktor g^(d/2)!

4. Algoritma Dijkstra

Algoritma ini mungkin yang paling terkenal untuk menemukan jalur terpendek. Keuntungannya dibandingkan pencarian DFS, BFS, dan dua arah adalah Anda dapat menggunakannya di semua grafik dengan bobot tepi positif. Jangan mencobanya pada graf yang mengandung bobot sisi negatif karena terminasi tidak dijamin dalam kasus ini.

Kursus Singkat: Antrian Prioritas

Untuk memahami algoritma Dijkstra, penting untuk memahami antrian prioritas. Antrian prioritas adalah struktur data abstrak yang memungkinkan operasi berikut:

  • isEmpty: memeriksa apakah antrian prioritas berisi elemen apapun
  • insert: menyisipkan elemen bersama dengan nilai prioritas
  • extractHighestPriority: mengembalikan elemen dengan prioritas tertinggi dan menghapusnya dari antrian prioritas

Apa yang dimaksud dengan prioritas? Secara matematis, prioritas harus memungkinkan urutan parsial untuk didefinisikan pada elemen antrian prioritas. Dalam kebanyakan kasus, itu adalah bilangan bulat sederhana p dan elemen dengan prioritas tertinggi adalah elemen dengan nilai terkecil (atau terbesar) untuk p. Dalam kasus kami, kami membutuhkan antrian prioritas untuk menyimpan semua node dalam grafik bersama dengan jaraknya ke node awal kami. Jadi operasi extractHighestPriority kami akan disebut extractMin, yang merupakan nama yang lebih deskriptif untuk mengambil node dengan jarak minimum ke node awal.

Bagaimana cara kerja algoritma Dijkstra?

Sebelum kita melihat kodenya, izinkan saya menjelaskan algoritme secara singkat sehingga Anda mendapatkan gambaran tentang cara kerjanya.

Kita mulai dengan menginisialisasi jalur terpendek dari node awal kita ke setiap node lain dalam grafik kita. Awalnya, ini akan menjadi tak terhingga untuk setiap node selain node awal itu sendiri. Node awal akan diinisialisasi dengan 0 karena itu adalah jarak ke dirinya sendiri. Kami memasukkan semua node ke antrian prioritas kami bersama dengan jarak yang sebelumnya diinisialisasi ke node awal kami sebagai prioritas.

Sekarang mulai pekerjaan yang sebenarnya. Sampai antrian prioritas tidak kosong, kami mengekstrak simpul dengan jarak terpendek yang diketahui saat ini ke simpul awal kami. Sebut saja currentNode. Kemudian kami mengulang semua tetangga dari currentNode, dan untuk masing-masing, kami memeriksa apakah mencapainya melalui currentNode lebih pendek dari jalur terpendek yang diketahui saat ini ke tetangga itu. Jika demikian, kami memperbarui jarak terpendek ke tetangga dan melanjutkan. Tapi lihat sendiri:

1. const dijkstra = (startNode, stopNode) => {
2.  const distances = new Map();
3.  const previous = new Map();
4.  const remaining = createPriorityQueue(n => distances.get(n));
5.  for (let node of adjacencyList.keys()) {
6.    distances.set(node, Number.MAX_VALUE);
7.    remaining.insert(node);
8.  }
9.  distances.set(startNode, 0);
10.
11.  while (!remaining.isEmpty()) {
12.    const n = remaining.extractMin();
13.    for (let neighbour of adjacencyList.get(n)) {
14.      const newPathLength = distances.get(n) + edgeWeights.get(n).get(neighbour);
15.      const oldPathLength = distances.get(neighbour);
16.      if (newPathLength < oldPathLength) {
17.        distances.set(neighbour, newPathLength);
18.        previous.set(neighbour, n);
20.      }
21.    }
22.  }
23.
24.  return { distance: distances.get(stopNode), path: previous };
25. };

Kami memberikan fungsi panggilan balik ke antrian prioritas yang memiliki akses ke peta jarak kami. Ini digunakan dalam implementasi antrian prioritas untuk mendapatkan jarak minimum. Namun, implementasi antrian prioritas tidak boleh dibahas dalam bagian ini.

Pertunjukan

Kompleksitas waktu dari algoritma ini sangat tergantung pada implementasi antrian prioritas. Misalkan n adalah jumlah simpul dan e adalah jumlah sisi dalam graf. Jika diimplementasikan dengan array sederhana, algoritma Dijkstra akan berjalan dalam O(n²). Namun, implementasi yang lebih umum menggunakan tumpukan Fibonacci sebagai antrian prioritas. Dalam hal ini, runtime berada dalam O(e + n log(n)).

5. Algoritma Bellman-Ford

Algoritma terakhir yang saya perkenalkan dalam cerita ini adalah algoritma Bellman-Ford. Berbeda dengan algoritma Dijkstra, dapat menangani bobot tepi negatif. Hanya ada satu batasan: Grafik tidak seharusnya mengandung siklus negatif. Siklus negatif adalah siklus yang ujung-ujungnya dijumlahkan dengan nilai negatif. Namun, algoritme mampu mendeteksi siklus negatif dan karenanya akan berhenti — meskipun tanpa jalur terpendek.

Algoritma ini sangat mirip dengan algoritma Dijkstra, tetapi tidak menggunakan antrian prioritas. Sebagai gantinya, ia berulang kali mengulang semua tepi, memperbarui jarak ke simpul awal dengan cara yang mirip dengan algoritma Dijkstra. Biarkan n lagi menjadi jumlah node dalam grafik kami. Algoritma Bellman-Ford mengulang tepat n-1 kali pada semua sisi karena jalur bebas siklus dalam graf tidak pernah dapat memuat lebih banyak sisi daripada n-1.

Setelah berulang kali mengulang semua tepi, algoritma mengulang semua tepi sekali lagi. Jika salah satu jarak masih belum optimal, berarti harus ada siklus negatif dalam grafik.

1. const bellmanFord = (startNode, stopNode) => {
2.  const distances = new Map();
3.  const previous = new Map();
4.  for (let node of adjacencyList.keys()) {
5.    distances.set(node, Number.MAX_VALUE);
6.  }
7.  distances.set(startNode, 0);
8.
9.  for (let i = 0; i < adjacencyList.size - 1; i++) {
10.    for (let n of adjacencyList.keys()) {
11.      for (let neighbour of adjacencyList.get(n)) {
12.        const newPathLength = distances.get(n) + edgeWeights.get(n).get(neighbour);
13.        const oldPathLength = distances.get(neighbour);
14.        if (newPathLength < oldPathLength) {
15.          distances.set(neighbour, newPathLength);
16.          previous.set(neighbour, n);
17.        }
18.      }
19.    }
20.  }
21.  for (let n of adjacencyList.keys()) {
22.    for (let neighbour of adjacencyList.get(n)) {
23.      if (distances.get(n) + edgeWeights.get(n).get(neighbour) < distances.get(neighbour)) {
24.        // there is a cycle with negative weight
25.        return null;
26.      }
27.    }
28.  }
29.
30.  return { distance: distances.get(stopNode), path: previous };
31. };

Pertunjukan

Kemampuan untuk menangani bobot tepi negatif ada harganya. Kompleksitas runtime dari algoritma Bellman-Ford adalah O(n * e). Oleh karena itu, Anda hanya boleh menggunakannya jika Anda benar-benar memiliki bobot tepi negatif.

Kesimpulan

Kami memeriksa beberapa algoritma yang paling penting untuk mendapatkan jalur terpendek dalam grafik, bersama dengan kelebihan dan kekurangannya. Mari kita lihat ikhtisar untuk membantu Anda memutuskan algoritme mana yang akan digunakan dalam situasi apa:

Seperti yang Anda lihat, algoritme mana yang digunakan bergantung pada beberapa properti grafik serta waktu proses algoritme. Namun, faktor penting lainnya adalah waktu implementasi. Jika Anda mengikuti kontes coding atau wawancara coding, maka kecepatan implementasi itu penting. Dalam hal ini, Anda mungkin ingin membuat trade-off antara kecepatan implementasi dan kompleksitas runtime. Semua pengamatan ini mengarah pada pertanyaan-pertanyaan berikut:

  • Apakah graf tersebut mengandung bobot sisi negatif?
  • Apakah graf tersebut mengandung bobot sisi positif > 1?
  • Apakah grafik mengandung siklus tak berarah?
  • Apakah kecepatan implementasi lebih penting daripada runtime?

Berdasarkan pertanyaan-pertanyaan ini, Anda dapat menentukan algoritma yang tepat untuk digunakan. Inilah pohon keputusan yang bermanfaat:

Harap dicatat bahwa bagian ini tidak mencakup semua algoritma yang ada untuk menemukan jalur terpendek dalam grafik. Ini memberikan gambaran tentang yang paling penting serta rekomendasi yang terbaik dari algoritma ini untuk situasi Anda.

Saya harap saya bisa memberi Anda pemahaman yang lebih dalam tentang lanskap ini sehingga Anda dapat memilih algoritme dengan bijak saat Anda membutuhkannya lagi.