DWGraph Algorithm

The DWGraph (Directed Weighted Graph) Algorithm is a graph-based algorithm primarily used to find the shortest path between nodes in a directed weighted graph. Directed weighted graphs, also known as networks, are a collection of vertices (nodes) connected by directed edges (arcs) with associated weights. The weights can represent distances, costs, or any other metrics associated with the connections between the nodes. The purpose of the DWGraph Algorithm is to determine the most efficient route, which is the path with the minimum sum of weights, from the source node to the target node, or all other nodes if desired. The most well-known implementation of the DWGraph Algorithm is Dijkstra's Algorithm, which guarantees the shortest path in a graph with non-negative edge weights. The algorithm initializes the distance from the source node to all other nodes as infinity, and the distance to itself as zero. It then iteratively selects the unvisited node with the lowest known distance from the source, calculates tentative distances to neighboring nodes through the current node, and updates the distances if a shorter path is found. The algorithm terminates when all nodes have been visited or it is confirmed that the shortest path to the target node has been found. Other algorithms such as Bellman-Ford and A* can also be used to solve the shortest path problem in directed weighted graphs, with the A* algorithm being particularly effective in graphs where a heuristic can be applied to guide the search towards the target node. 
/*
 * Copyright (c) 2017 Kotlin Algorithm Club
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all
 * copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
 
package com.algorithmexamples.graphs.directed.weighted
 
import com.algorithmexamples.datastructures.Queue
import com.algorithmexamples.datastructures.Stack
import com.algorithmexamples.graphs.Graph
 
class DWGraph(public override val V: Int): Graph {
    public override var E: Int = 0
    private val adj: Array<Queue<Edge>> = Array(V) { Queue<Edge>() }
    private val indegree: IntArray = IntArray(V)
 
    public class Edge(public val from: Int, public val to: Int, public val weight: Double)
 
    public fun addEdge(from: Int, to: Int, weight: Double) {
        val edge = Edge(from, to, weight)
        adj[from].add(edge)
        indegree[to]++
        E++
    }
 
    public fun edges(): Collection<Edge> {
        val stack = Stack<Edge>()
        adj.flatMap { it }.forEach { stack.push(it) }
        return stack
    }
 
    public fun adjacentEdges(from: Int): Collection<Edge> {
        return adj[from]
    }
 
    public override fun adjacentVertices(from: Int): Collection<Int> {
        return adjacentEdges(from).map { it.to }
    }
 
    public fun outdegree(v: Int): Int {
        return adj[v].size
    }
}

LANGUAGE:

DARK MODE:

PROGRAMMING LANGUAGES:

Python

Java

Javascript

C#

C++

C

Ruby

Scala

MATLAB

Kotlin

Rust

R

Go