DFS JARAK

Oleh Johannes -
class Node:
    def __init__(self,name):
        self.name = name
    def getName(self):
        return self.name
    def __str__(self):
        return self.name

class Edge:
    def __init__(self, asal, tujuan, jarak):
        self.asal = asal
        self.tujuan = tujuan
        self.jarak = jarak
    def getAsal(self):
        return self.asal
    def getTujuan(self):
        return self.tujuan
    def getJarak(self):
        return self.jarak
    def __str__(self):
        return f"{self.asal.getName()} -> {self.tujuan.getName()} ({self.jarak} km)"

class Digraph:
    def __init__(self):
        self.edge = {}
    def addNode(self,node):
        if node in self.edge:
            raise ValueError("Sudah ada")  
        else:
            self.edge[node] = []
    def addEdge(self, edge):
        asal = edge.getAsal()
        tujuan = edge.getTujuan()
        jarak = edge.getJarak()

        if not (asal in self.edge and tujuan in self.edge):
            raise ValueError("Node tidak ada")
        else:
            self.edge[asal].append((tujuan, jarak))
    def getNode(self, node):
        for n in self.edge:
            if n.getName() == node:
                return n
        raise NameError(f"Node '{node}' tidak ditemukan")
    def childrenOf(self,node):
        return self.edge[node]
    def __str__(self):
        res = ""
        for src in self.edge:
            for dest in self.edge[src]:
                res += res + f"{src} -> {dest}"
        return res
class Graph(Digraph):
    def addEdge(self, edge):
        return super().addEdge(edge)
       

def printPath(path):
    result = ""
    for i in range(len(path)):
        result += str(path[i])
        if i != len(path)-1:
            result += "->"
       
    return result


def dfs(graph,asal,tujuan,shortest,path=[],toPrint=False):
    path = path + [asal]
    if toPrint:
        print(printPath(path))
    if asal == tujuan:
        return path
    for nextNode in graph.childrenOf(asal):
        if nextNode not in path:
            if shortest == None or len(path) < len(shortest):
                newPath = dfs(graph,nextNode,tujuan,shortest,path,toPrint)

                if newPath != None:
                    shortest = newPath
       

    return shortest


def dfs(graph, asal, tujuan, path=None, jarak=0,
        shortest=None, toPrint=False):

    if path is None:
        path = []

    path = path + [asal]

    if asal == tujuan:
        if toPrint:
            print(f"{printPath(path)} = {jarak} km")

        if shortest is None or jarak < shortest[1]:
            return (path, jarak)

        return shortest

    if toPrint:
        print(f"{printPath(path)} = {jarak} km")

    for nextNode, bobot in graph.childrenOf(asal):

        if nextNode not in path:

            # Pangkas jalur jika sudah lebih panjang
            # daripada jarak terbaik yang ditemukan
            if shortest is None or jarak + bobot < shortest[1]:

                hasil = dfs(
                    graph,
                    nextNode,
                    tujuan,
                    path,
                    jarak + bobot,
                    shortest,
                    toPrint
                )

                if hasil is not None:
                    if shortest is None or hasil[1] < shortest[1]:
                        shortest = hasil

    return shortest




g = Digraph()

# Create 7 nodes
for name in (
    'Boston',
    'Providence',
    'New York',
    'Chicago',
    'Denver',
    'Phoenix',
    'Los Angeles'
):

    g.addNode(Node(name))

# Create edges

g.addEdge(Edge(g.getNode('Boston'),
               g.getNode('Providence'), 80))

g.addEdge(Edge(g.getNode('Boston'),
               g.getNode('New York'), 300))

g.addEdge(Edge(g.getNode('Providence'),
               g.getNode('Boston'), 80))

g.addEdge(Edge(g.getNode('Providence'),
               g.getNode('New York'), 250))

g.addEdge(Edge(g.getNode('New York'),
               g.getNode('Chicago'), 1_150))

g.addEdge(Edge(g.getNode('Chicago'),
               g.getNode('Denver'), 1_000))

g.addEdge(Edge(g.getNode('Chicago'),
               g.getNode('Phoenix'), 1_750))

g.addEdge(Edge(g.getNode('Denver'),
               g.getNode('Phoenix'), 950))

g.addEdge(Edge(g.getNode('Denver'),
               g.getNode('New York'), 2_600))

g.addEdge(Edge(g.getNode('Los Angeles'),
               g.getNode('Boston'), 4_800))




hasil = dfs(
    g,
    g.getNode("Boston"),
    g.getNode("Phoenix"),
    toPrint=True
)

if hasil is not None:
    jalur, totalJarak = hasil

    print("\nJalur terpendek:", printPath(jalur))
    print("Total jarak:", totalJarak, "km")
else:
    print("Jalur tidak ditemukan")


   
   

Komentar

Posting Komentar

Postingan populer dari blog ini

Analisis Data Menggunakan Orange

Oleh Johannes -
Gambar
  Setiap hari, kita disuguhkan berbagai visualisasi data yang keren—seperti grafik jumlah penonton TikTok, infografis di berita, atau diagram nilai ujian. Pernahkah kalian bertanya, bagaimana data mentah bisa berubah menjadi gambar yang informatif dan mudah dipahami? Di tengah banjir data dari media sosial, cuaca, hingga hasil belajar, kita perlu alat yang bisa membantu mengolah dan menyajikan informasi tersebut dengan cara yang menarik. Nah, hari ini kita akan mencoba menjadi ilmuwan data pemula! Tanpa perlu menulis kode, kita akan belajar menganalisis data hanya dengan drag, klik, dan sambung menggunakan alat yang menyenangkan: Orange Data Mining . Siap menerima tantangan dan menjelajahi dunia data seperti ilmuwan sungguhan?   Penjelasan Konsep (teori) Saat ini, kita hidup di era di mana data sangat melimpah—mulai dari data belanja online, hasil ujian, hingga jumlah penonton YouTube. Tapi bagaimana cara kita mengubah data yang kompleks menjadi informasi yang mudah dipa...
Baca selengkapnya

Pengenalan Bahasa C

Oleh -
Pengenalan Bahasa Pemrograman C Oleh: Johannes Alexander Putra, S.Pd.  Alumni Pendidikan Ilmu Komputer, Universitas Pendidikan Indonesia (UPI) Bumi Siliwangi Bandung Apa itu C? C adalah bahasa pemrograman serba guna yang diciptakan oleh Dennis Ritchie di Bell Laboratories pada tahun 1972. Ini adalah bahasa yang sangat populer, meskipun sudah tua. C sangat terkait dengan UNIX, karena dikembangkan untuk menulis sistem operasi UNIX Mengapa Belajar Bahasa C? Ini adalah salah satu bahasa pemrograman paling populer di dunia  Jika Anda menguasai C, Anda tidak akan kesulitan mempelajari bahasa pemrograman populer lainnya seperti Java, Python, C++, C#, dll, karena sintaksnya mirip  C sangat cepat, dibandingkan dengan bahasa pemrograman lain, seperti Java dan Python  Bahasa C sangat serbaguna; dapat digunakan dalam aplikasi dan teknologi Perbedaan antara C dan C++ C++ dikembangkan sebagai perluasan dari C, dan kedua bahasa tersebut memiliki sintaks yang hampir sama Perbedaan u...
Baca selengkapnya

Pengalaman Test ELPT ITB

Oleh -
Overview Pada postingan kali ini saya akan membagikan pengalaman mengikuti ELPT di Institut Teknologi Bandung. Singkatnya ELPT itu adalah test untuk menguji kemampuan berbahasa inggris dengan format menyerupai TOEFL ITP. Dalam test ini kemampuan listening, structure (grammar), dan reading  seseorang akan diuji. Test ini digunakan untuk menggantikan TOEFL ITP sebagai syarat pendaftaran pascasarjana dan syarat kelulusan jenjang S2 dan S3.  Harga Biaya yang dikeluarkan untuk mengikuti Test ELPT ini secara offline adalah Rp.250.000. Harga tersebut lumayan cukup besar. Pengalaman saya mengikuti test serupa di kampus PTN lain seperti di UPI yaitu test PTESOL adalah Rp80.000 untuk mahasiswa UPI dan Rp.150.000 untuk umum. Format Test Format test yang digunakan adalah test dibagi menjadi 3 sesi yaitu listening, structure, dan reading. Kurang lebih sama seperti test TOEFL pada umumnya. Saya mengikuti test secara offline, maka saya mengerjakan di kertas LJU bukan menggunakan komputer. Pe...
Baca selengkapnya