Forem: fy

Finding Shortest Paths in a Graph - Dijkstra's Algorithm

fy — Thu, 12 Aug 2021 15:37:50 +0000

Dijkstra's algorithm is used to find the shortest path(s) from node x to all its connected nodes.

Consider the following weighted graph.

Whats the shortest path from node 0 to node 3?

We can look at the followings possible paths

7: 0 <--> 3
11: 0 <--> 4 <--> 3
7: 0 <--> 1 <--> 3
6: 0 <--> 1 <--> 2 <--> 3

The fourth path is the shortest path since we can look at the edges and see how long it will take to get there. But this is a small example, we can have graphs with millions of nodes and edges.

So how do we do this programmatically?

There are many algorithms for finding the shortest path between nodes within a graph but the focus here is Dijkstra's algorithm.

Implementation steps:

Use DFS to visit the smallest nodes first.
Compare parent distance and edge weight with node distance. In case it's less than infinity or calculated distance then update it.
Use recursive programming to visit the smallest nodes.

Code:
Add Vertex and Path classes

data class Vertex(val name: String, var distance: Int = Int.MAX_VALUE, var visited: Boolean = false)
{
    val linkedEdges = mutableListOf<Path>()

    fun addEdges(edges: List<Path>) {
        edges.sortedBy { it.weight }.forEach {
            linkedEdges.add(it)
        }
    }
}

data class Path(val start: Vertex, val end: Vertex, val weight: Int)

Add a row class, this is used to print a table row at the end

data class DistanceRow(val to: String, val distance: Int, val via: String, ) {
    override fun toString(): String {
        return """
             $to | $distance | $via
        """.trimIndent()
    }
}

Dijkstra's algorithm

class Dijkstra {
    val distances = mutableListOf<DistanceRow>()

    fun shortestPath(vertex: Vertex, d: Int = 0) {
        vertex.visited = true

        for (edge in vertex.linkedEdges) {
            val distance = d + edge.weight
            val connectedEdge = edge.end

            if (distance < connectedEdge.distance) {
                connectedEdge.distance = distance
                distances.add(DistanceRow(connectedEdge.name, distance, vertex.name))
            }
            if (!connectedEdge.visited) {
                shortestPath(connectedEdge, connectedEdge.distance)
            }
        }
    }
}

Running the code

fun main() {
    val zero = Vertex("0")
    val one = Vertex("1")
    val two = Vertex("2")
    val three = Vertex("3")
    val four = Vertex("4")

    zero.addEdges(listOf(
        Path(zero, one, 3),
        Path(zero, four, 8),
        Path(zero, three, 7),
    ))

    one.addEdges(listOf(
        Path(one, two, 1),
        Path(one, three, 4),
    ))

    two.addEdges(listOf(
        Path(two, three, 2),
    ))

    three.addEdges(listOf(
        Path(three, two, 2),
    ))

    four.addEdges(listOf(
        Path(four, three, 3)
    ))

    Dijkstra().apply {
        shortestPath(zero)
        print("Distances:\n---------------\nTo|Dist|Via\n---------------\n")
        distances.forEach {
            println(it)
        }
    }

}

Output:

Distances:
---------------
To|Dist|Via
---------------
1 | 3 | 0
2 | 4 | 1
3 | 6 | 2
4 | 8 | 0

Note: The example focuses on finding the shortest path from node 0 to node 3 therefore the edges have more connectivity between these nodes. Some edges are still undirected. Add directed edges for other nodes if needed.

Src code: https://github.com/faizzed/datastructures-algorithms/blob/master/src/main/kotlin/algorithms/graphs/DijkstraShortestPath.kt

Kotlin, classes inside interface, interface inside classes, sealed classes, data classes and so on.

fy — Sat, 19 Dec 2020 10:34:23 +0000

I recently started reading kotlin docs, it has a lot of features in oop. Its cool but at the same time i can't help but wonder why do we need this? I was doing fine with data class, sealed class, inner class and such but interfaces inside classes, classes inside interfaces and so on just blew my fuse.

interface AnInterfaceIsJustAContractNothingMore {
    class WaitUntilYouCodeInKotlin {
        fun OhNo(): String {
            return "I cant even tell the difference anymore. Its like blending diff realities."
        }

        interface ThisWorksToo {
            class EvenThis {
                val why = "Why do i need this?"
            }
        }
    }
}

I am writing this to express my opinion at the same time have some opinions on how other people feel about this?

Golang - why is function return type always byte ([])?

fy — Sun, 14 Jun 2020 16:12:54 +0000

Most of the packages in golang return response in byte ([]).

e.g if you do

exec.Command("ls").Output() or http.Get("http://example.com") or anything else, the response is in byte ([]).

whats the reasoning behind this?

Covid19 pandemic charts

fy — Fri, 27 Mar 2020 18:56:07 +0000

check it out

There are numerous covid19 resources out there at this point. People use different resources in a different way to understand the spread of the virus. I found other resources a bit limiting except this one. But anyway being a dev, i had an itch to create my own, or something to help me see what i wanted to see during this tragic time.

Now that i have it, i want to share it, i have created a log where i will check everyday who visited my charts :D sad! i know.

Good luck people! stay safe!

golang, why doesn't string type inherit all the methods of strings package?

fy — Tue, 24 Mar 2020 16:11:19 +0000

I am too scared to write this question on stackOverflow because those guys will feed me to the wolves, something unique about golang community! they are a ruthless bunch on SO.

Getting back to the point, basically the question. i know you can do something like

type Str string

func (s Str) toByteArr() {
    fmt.Println([].byte(s))
}

func main()  {
    Str("Looking good today!").toByteArr()
}

But this kind of open gates for all kind of types floating around and i imagine could become harder to handle at some point.

I am just thinking wouldn't it be easy like any other language "string".method(); to have all those methods from strings package available to you, rather then you trying to find ways how to make this more easy to write strings.doSomething(myString).

If not, what is the reason?

Aws services are horrible

fy — Tue, 11 Feb 2020 06:14:04 +0000

I am a backend dev who has to do stuff on aws from time to time. Yesterday, i had to give access to billing to one of colleague. It took me almost 4 to 5 hours for a task that takes almost zero amount of time on other sites.

It makes me criticize the way how things work on aws. The services are not easy to understand, at the same time documentation is horrible i had to find the information in 3 different places from 3 different topics. The forum is absolutely shit! please. Maybe i am ignorant to the fact that how awesome aws is, but its not. Simplicity is missing.