# Find if there is a path of more than k length from a source

The problem you're addressing is to find whether there exists a path of more than a given length 'k' starting from a given source node in a graph. The graph is represented as an adjacency list where each vertex is connected to other vertices with associated lengths.

## Problem Statement and Example

Given a graph with vertices and edges, you need to determine if there is a path starting from a specified source node such that the sum of lengths of the edges along the path is greater than a specified value 'k'. For example, consider the following graph:

``````Vertices: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
Edges: (0,1,9), (0,2,10), (0,9,4), (1,3,6), (1,9,5), (2,4,3), (2,7,7), (2,9,2), (3,5,5), (3,7,4), (3,9,3), (4,6,4), (5,6,3), (5,7,8), (6,7,8), (6,8,4)``````

In this graph, you're required to find if there is a path of length greater than 'k' starting from a specified source node.

## Idea to Solve

To solve this problem, you can perform Depth-First Search (DFS) starting from the source node. During the DFS traversal, you'll keep track of the length of the path. If the length exceeds 'k', you can immediately return 'true'. You'll also maintain a visited array to avoid revisiting nodes that are already part of the current path.

## Pseudocode

``````function isLengthGreaterThanK(index, visit, sum, k)
if index is out of bounds
return false
if visit[index] is true
return false
if sum > k
return true
set visit[index] to true
for each neighbor of index
if isLengthGreaterThanK(neighbor, visit, sum + length of edge, k)
return true
set visit[index] to false
return false

function checkPathGreaterThanK(source, k)
create visit array of size equal to number of vertices
set all elements of visit array to false
if isLengthGreaterThanK(source, visit, 0, k)
print "Result: YES"
else
print "Result: NO"``````

## Algorithm Explanation

1. Implement a recursive function `isLengthGreaterThanK(index, visit, sum, k)` that checks whether there is a path starting from 'index' with a length greater than 'k'.
2. The function first checks if 'index' is within bounds and if the node has already been visited. If so, it returns false.
3. If the sum of the path is greater than 'k', it returns true.
4. Set the visited status of 'index' to true.
5. Iterate through the neighbors of 'index'. For each neighbor, recursively call the function with updated values for 'index', 'visit', 'sum', and 'k'.
6. After trying all neighbors, reset the visited status of 'index' and return false.
7. Implement `checkPathGreaterThanK(source, k)` that initializes the visited array, then calls `isLengthGreaterThanK()` for the source node. Print the result.

## Program Solution

``````/*
Java Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
public int id;
public int length;
public AjlistNode next;
public AjlistNode(int id, int length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
public int data;
public AjlistNode next;
public Vertices(int data)
{
this.data = data;
this.next = null;
}
}
public class Graph
{
// Number of Vertices
public int size;
public Vertices[] node;
public Graph(int size)
{
//set value
this.size = size;
this.node = new Vertices[size];
this.setData();
}
// Set initial node value
public void setData()
{
if (node == null)
{
System.out.println("\nEmpty Graph");
}
else
{
for (int index = 0; index < size; index++)
{
node[index] = new Vertices(index);
}
}
}
// Connect two nodes
public void connect(int start, int last, int length)
{
AjlistNode new_edge = new AjlistNode(last, length);
if (node[start].next == null)
{
node[start].next = new_edge;
}
else
{
AjlistNode temp = node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
public void addEdge(int start, int last, int length)
{
if (start >= 0 && start < size && last >= 0 &&
last < size && node != null)
{
connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
connect(last, start, length);
}
else
{
System.out.println("\nHere Something Wrong");
}
}
public void printGraph()
{
if (size > 0 && node != null)
{
// Print graph ajlist Node value
for (int index = 0; index < size; ++index)
{
System.out.print("\nAdjacency list of vertex " +
index + " :");
AjlistNode temp = node[index].next;
while (temp != null)
{
System.out.print("  " + node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
public boolean isLengthGreaterThanK(
int index, boolean[] visit, int sum, int k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode temp = node[index].next;
while (temp != null)
{
if (isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
public void checkPathGreaterThanK(int source, int k)
{
boolean[] visit = new boolean[this.size];
// Set initial visited node status
for (int i = 0; i < size; ++i)
{
visit[i] = false;
}
System.out.print("\n Source node : " + source);
System.out.print("\n Length  k : " + k);
if (isLengthGreaterThanK(source, visit, 0, k))
{
System.out.print("\n Result : YES\n");
}
else
{
System.out.print("\n Result : NO\n");
}
}
public static void main(String[] args)
{
// 10 implies the number of nodes in graph
Graph g = new Graph(10);
// print graph element
g.printGraph();
// Test A
int source = 0;
int k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````// Include header file
#include <iostream>
using namespace std;
/*
C++ Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
public:
// Vertices node key
int id;
int length;
AjlistNode *next;

AjlistNode(int id, int length)
{
// Set value of node key
this->id = id;
this->length = length;
this->next = NULL;
}
};
class Vertices
{
public: int data;
AjlistNode *next;
Vertices()
{
this->data = 0;
this->next = NULL;
}
Vertices(int data)
{
this->data = data;
this->next = NULL;
}
};
class Graph
{
public:
// Number of Vertices
int size;
Vertices *node;
Graph(int size)
{
//set value
this->size = size;
this->node = new Vertices[size];
this->setData();
}
// Set initial node value
void setData()
{
if (this->node == NULL)
{
cout << "\nEmpty Graph" << endl;
}
else
{
for (int index = 0; index < this->size; index++)
{
this->node[index].data = index;
}
}
}
// Connect two nodes
void connect(int start, int last, int length)
{
AjlistNode *new_edge = new AjlistNode(last, length);
if (this->node[start].next == NULL)
{
this->node[start].next = new_edge;
}
else
{
AjlistNode *temp = this->node[start].next;
while (temp->next != NULL)
{
temp = temp->next;
}
temp->next = new_edge;
}
}
// Add edge of two nodes
void addEdge(int start, int last, int length)
{
if (start >= 0 && start < this->size &&
last >= 0 && last < this->size && this->node != NULL)
{
this->connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this->connect(last, start, length);
}
else
{
cout << "\nHere Something Wrong" << endl;
}
}
void printGraph()
{
if (this->size > 0 && this->node != NULL)
{
// Print graph ajlist Node value
for (int index = 0; index < this->size; ++index)
{
cout << "\nAdjacency list of vertex " << index << " :";
AjlistNode *temp = this->node[index].next;
while (temp != NULL)
{
cout << "  " << this->node[temp->id].data;
// visit to next edge
temp = temp->next;
}
}
}
}
bool isLengthGreaterThanK(int index, bool visit[], int sum, int k)
{
if (index < 0 || index >= this->size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode *temp = this->node[index].next;
while (temp != NULL)
{
if (this->isLengthGreaterThanK(
temp->id, visit, sum + (temp->length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp->next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
void checkPathGreaterThanK(int source, int k)
{
bool visit[this->size];
// Set initial visited node status
for (int i = 0; i < this->size; ++i)
{
visit[i] = false;
}
cout << "\n Source node : " << source;
cout << "\n Length  k : " << k;
if (this->isLengthGreaterThanK(source, visit, 0, k))
{
cout << "\n Result : YES\n";
}
else
{
cout << "\n Result : NO\n";
}
}
};
int main()
{
// 10 implies the number of nodes in graph
Graph *g = new Graph(10);
// print graph element
g->printGraph();
// Test A
int source = 0;
int k = 48;
g->checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g->checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g->checkPathGreaterThanK(source, k);
return 0;
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````// Include namespace system
using System;
/*
Csharp Program for
Find if there is a path of more than k length from a source
*/
public class AjlistNode
{
// Vertices node key
public int id;
public int length;
public AjlistNode next;
public AjlistNode(int id, int length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
public class Vertices
{
public int data;
public AjlistNode next;
public Vertices(int data)
{
this.data = data;
this.next = null;
}
}
public class Graph
{
// Number of Vertices
public int size;
public Vertices[] node;
public Graph(int size)
{
//set value
this.size = size;
this.node = new Vertices[size];
this.setData();
}
// Set initial node value
public void setData()
{
if (this.node == null)
{
Console.WriteLine("\nEmpty Graph");
}
else
{
for (int index = 0; index < this.size; index++)
{
this.node[index] = new Vertices(index);
}
}
}
// Connect two nodes
public void connect(int start, int last, int length)
{
AjlistNode new_edge = new AjlistNode(last, length);
if (this.node[start].next == null)
{
this.node[start].next = new_edge;
}
else
{
AjlistNode temp = this.node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
public void addEdge(int start, int last, int length)
{
if (start >= 0 && start < this.size && last >= 0 &&
last < this.size && this.node != null)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
Console.WriteLine("\nHere Something Wrong");
}
}
public void printGraph()
{
if (this.size > 0 && this.node != null)
{
// Print graph ajlist Node value
for (int index = 0; index < this.size; ++index)
{
Console.Write("\nAdjacency list of vertex " + index + " :");
AjlistNode temp = this.node[index].next;
while (temp != null)
{
Console.Write("  " + this.node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
public Boolean isLengthGreaterThanK(int index,
Boolean[] visit, int sum, int k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
AjlistNode temp = this.node[index].next;
while (temp != null)
{
if (this.isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
public void checkPathGreaterThanK(int source, int k)
{
Boolean[] visit = new Boolean[this.size];
// Set initial visited node status
for (int i = 0; i < this.size; ++i)
{
visit[i] = false;
}
Console.Write("\n Source node : " + source);
Console.Write("\n Length  k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
Console.Write("\n Result : YES\n");
}
else
{
Console.Write("\n Result : NO\n");
}
}
public static void Main(String[] args)
{
// 10 implies the number of nodes in graph
Graph g = new Graph(10);
// print graph element
g.printGraph();
// Test A
int source = 0;
int k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````package main
import "fmt"
/*
Go Program for
Find if there is a path of more than k length from a source
*/
type AjlistNode struct {
// Vertices node key
id int
length int
next * AjlistNode
}
func getAjlistNode(id int, length int) * AjlistNode {
var me *AjlistNode = &AjlistNode {}
// Set value of node key
me.id = id
me.length = length
me.next = nil
return me
}
type Vertices struct {
data int
next * AjlistNode
}
func getVertices(data int) * Vertices {
var me *Vertices = &Vertices {}
me.data = data
me.next = nil
return me
}
type Graph struct {
// Number of Vertices
size int
node []*Vertices
}
func getGraph(size int) * Graph {
var me *Graph = &Graph {}
//set value
me.size = size
me.node = make([]*Vertices, size)
me.setData()
return me
}
// Set initial node value
func(this *Graph) setData() {
if this.node == nil {
fmt.Println("\nEmpty Graph")
} else {
for index := 0 ; index < this.size ; index++ {
this.node[index] = getVertices(index)
}
}
}
// Connect two nodes
func(this *Graph) connect(start, last, length int) {
var new_edge * AjlistNode = getAjlistNode(last, length)
if this.node[start].next == nil {
this.node[start].next = new_edge
} else {
var temp * AjlistNode = this.node[start].next
for (temp.next != nil) {
temp = temp.next
}
temp.next = new_edge
}
}
// Add edge of two nodes
func(this *Graph) addEdge(start, last, length int) {
if start >= 0 && start < this.size && last >= 0 &&
last < this.size && this.node != nil {
this.connect(start, last, length)
if start == last {
// Self looping situation
return
}
this.connect(last, start, length)
} else {
fmt.Println("\nHere Something Wrong")
}
}
func(this Graph) printGraph() {
if this.size > 0 && this.node != nil {
// Print graph ajlist Node value
for index := 0 ; index < this.size ; index++ {
fmt.Print("\nAdjacency list of vertex ", index, " :")
var temp * AjlistNode = this.node[index].next
for (temp != nil) {
fmt.Print("  ", this.node[temp.id].data)
// visit to next edge
temp = temp.next
}
}
}
}
func(this Graph) isLengthGreaterThanK(
index int, visit[] bool, sum int, k int) bool {
if index < 0 || index >= this.size {
return false
}
if visit[index] == true {
// When node is already includes in current path
return false
}
if sum > k {
// When length sum is greater than k
return true
}
// Here modified  the value of visited node
visit[index] = true
// This is used to iterate nodes edges
var temp * AjlistNode = this.node[index].next
for (temp != nil) {
if this.isLengthGreaterThanK(temp.id,
visit, sum + (temp.length), k) {
// Found path with length greater than k
return true
}
// Visit to next edge
temp = temp.next
}
// Reset the value of visited node status
visit[index] = false
return false
}
func(this Graph) checkPathGreaterThanK(source, k int) {
// Set initial visited node status
var visit = make([] bool, this.size)
fmt.Print("\n Source node : ", source)
fmt.Print("\n Length  k : ", k)
if this.isLengthGreaterThanK(source, visit, 0, k) {
fmt.Print("\n Result : YES\n")
} else {
fmt.Print("\n Result : NO\n")
}
}
func main() {
// 10 implies the number of nodes in graph
var g * Graph = getGraph(10)
// print graph element
g.printGraph()
// Test A
var source int = 0
var k int = 48
g.checkPathGreaterThanK(source, k)
// Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
// Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES
``````
``````<?php
/*
Php Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
public \$id;
public \$length;
public \$next;
public	function __construct(\$id, \$length)
{
// Set value of node key
\$this->id = \$id;
\$this->length = \$length;
\$this->next = NULL;
}
}
class Vertices
{
public \$data;
public \$next;
public	function __construct(\$data)
{
\$this->data = \$data;
\$this->next = NULL;
}
}
class Graph
{
// Number of Vertices
public \$size;
public \$node;
public	function __construct(\$size)
{
//set value
\$this->size = \$size;
\$this->node = array_fill(0, \$size, NULL);
\$this->setData();
}
// Set initial node value
public	function setData()
{
if (\$this->node == NULL)
{
echo("\nEmpty Graph\n");
}
else
{
for (\$index = 0; \$index < \$this->size; \$index++)
{
\$this->node[\$index] = new Vertices(\$index);
}
}
}
// Connect two nodes
public	function connect(\$start, \$last, \$length)
{
\$new_edge = new AjlistNode(\$last, \$length);
if (\$this->node[\$start]->next == NULL)
{
\$this->node[\$start]->next = \$new_edge;
}
else
{
\$temp = \$this->node[\$start]->next;
while (\$temp->next != NULL)
{
\$temp = \$temp->next;
}
\$temp->next = \$new_edge;
}
}
// Add edge of two nodes
{
if (\$start >= 0 && \$start < \$this->size &&
\$last >= 0 && \$last < \$this->size && \$this->node != NULL)
{
\$this->connect(\$start, \$last, \$length);
if (\$start == \$last)
{
// Self looping situation
return;
}
\$this->connect(\$last, \$start, \$length);
}
else
{
echo("\nHere Something Wrong\n");
}
}
public	function printGraph()
{
if (\$this->size > 0 && \$this->node != NULL)
{
// Print graph ajlist Node value
for (\$index = 0; \$index < \$this->size; ++\$index)
{
echo("\nAdjacency list of vertex ".\$index." :");
\$temp = \$this->node[\$index]->next;
while (\$temp != NULL)
{
echo("  ".\$this->node[\$temp->id]->data);
// visit to next edge
\$temp = \$temp->next;
}
}
}
}
public	function isLengthGreaterThanK(\$index, \$visit, \$sum, \$k)
{
if (\$index < 0 || \$index >= \$this->size)
{
return false;
}
if (\$visit[\$index] == true)
{
// When node is already includes in current path
return false;
}
if (\$sum > \$k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
\$visit[\$index] = true;
// This is used to iterate nodes edges
\$temp = \$this->node[\$index]->next;
while (\$temp != NULL)
{
if (\$this->isLengthGreaterThanK(\$temp->id,
\$visit, \$sum + (\$temp->length), \$k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
\$temp = \$temp->next;
}
// Reset the value of visited node status
\$visit[\$index] = false;
return false;
}
public	function checkPathGreaterThanK(\$source, \$k)
{
\$visit = array_fill(0, \$this->size, false);

echo("\n Source node : ".\$source);
echo("\n Length  k : ".\$k);
if (\$this->isLengthGreaterThanK(\$source, \$visit, 0, \$k))
{
echo("\n Result : YES\n");
}
else
{
echo("\n Result : NO\n");
}
}
}

function main()
{
// 10 implies the number of nodes in graph
\$g = new Graph(10);
// print graph element
\$g->printGraph();
// Test A
\$source = 0;
\$k = 48;
\$g->checkPathGreaterThanK(\$source, \$k);
// Test B
\$source = 0;
\$k = 51;
\$g->checkPathGreaterThanK(\$source, \$k);
// Test C
\$source = 8;
\$k = 54;
\$g->checkPathGreaterThanK(\$source, \$k);
}
main();``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````/*
Node JS Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
constructor(id, length)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
constructor(data)
{
this.data = data;
this.next = null;
}
}
class Graph
{
constructor(size)
{
//set value
this.size = size;
this.node = Array(size).fill(null);
this.setData();
}
// Set initial node value
setData()
{
if (this.node == null)
{
console.log("\nEmpty Graph");
}
else
{
for (var index = 0; index < this.size; index++)
{
this.node[index] = new Vertices(index);
}
}
}
// Connect two nodes
connect(start, last, length)
{
var new_edge = new AjlistNode(last, length);
if (this.node[start].next == null)
{
this.node[start].next = new_edge;
}
else
{
var temp = this.node[start].next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
{
if (start >= 0 && start < this.size &&
last >= 0 && last < this.size && this.node != null)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
console.log("\nHere Something Wrong");
}
}
printGraph()
{
if (this.size > 0 && this.node != null)
{
// Print graph ajlist Node value
for (var index = 0; index < this.size; ++index)
{
process.stdout.write("\nAdjacency list of vertex " +
index + " :");
var temp = this.node[index].next;
while (temp != null)
{
process.stdout.write("  " + this.node[temp.id].data);
// visit to next edge
temp = temp.next;
}
}
}
}
isLengthGreaterThanK(index, visit, sum, k)
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp = this.node[index].next;
while (temp != null)
{
if (this.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
checkPathGreaterThanK(source, k)
{
// Set initial visited node status
var visit = Array(this.size).fill(false);
process.stdout.write("\n Source node : " + source);
process.stdout.write("\n Length  k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
process.stdout.write("\n Result : YES\n");
}
else
{
process.stdout.write("\n Result : NO\n");
}
}
}

function main()
{
// 10 implies the number of nodes in graph
var g = new Graph(10);
// print graph element
g.printGraph();
// Test A
var source = 0;
var k = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
main();``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````#    Python 3 Program for
#    Find if there is a path of more than k length from a source
class AjlistNode :
#  Vertices node key
def __init__(self, id, length) :
#  Set value of node key
self.id = id
self.length = length
self.next = None

class Vertices :
def __init__(self, data) :
self.data = data
self.next = None

class Graph :
#  Number of Vertices
def __init__(self, size) :
# set value
self.size = size
self.node = [None] * (size)
self.setData()

#  Set initial node value
def setData(self) :
if (self.node == None) :
print("\nEmpty Graph")
else :
index = 0
while (index < self.size) :
self.node[index] = Vertices(index)
index += 1

#  Connect two nodes
def connect(self, start, last, length) :
new_edge = AjlistNode(last, length)
if (self.node[start].next == None) :
self.node[start].next = new_edge
else :
temp = self.node[start].next
while (temp.next != None) :
temp = temp.next

temp.next = new_edge

#  Add edge of two nodes
def addEdge(self, start, last, length) :
if (start >= 0 and start < self.size and
last >= 0 and last < self.size and self.node != None) :
self.connect(start, last, length)
if (start == last) :
#  Self looping situation
return

self.connect(last, start, length)
else :
print("\nHere Something Wrong")

def printGraph(self) :
if (self.size > 0 and self.node != None) :
index = 0
#  Print graph ajlist Node value
while (index < self.size) :
index ," :", end = "")
temp = self.node[index].next
while (temp != None) :
print("  ", self.node[temp.id].data, end = "")
#  visit to next edge
temp = temp.next

index += 1

def isLengthGreaterThanK(self, index, visit, sum, k) :
if (index < 0 or index >= self.size) :
return False

if (visit[index] == True) :
#  When node is already includes in current path
return False

if (sum > k) :
#  When length sum is greater than k
return True

#  Here modified  the value of visited node
visit[index] = True
#  This is used to iterate nodes edges
temp = self.node[index].next
while (temp != None) :
if (self.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k)) :
#  Found path with length greater than k
return True

#  Visit to next edge
temp = temp.next

#  Reset the value of visited node status
visit[index] = False
return False

def checkPathGreaterThanK(self, source, k) :
#  Set initial visited node status
visit = [False] * (self.size)
print("\n Source node : ", source, end = "")
print("\n Length  k : ", k, end = "")
if (self.isLengthGreaterThanK(source, visit, 0, k)) :
print("\n Result : YES")
else :
print("\n Result : NO")

def main() :
#  10 implies the number of nodes in graph
g = Graph(10)
#  print graph element
g.printGraph()
#  Test A
source = 0
k = 48
g.checkPathGreaterThanK(source, k)
#  Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
#  Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)

if __name__ == "__main__": main()``````

#### Output

``````Adjacency list of vertex  0  :   1   2   9
Adjacency list of vertex  1  :   0   3   9
Adjacency list of vertex  2  :   0   4   7   9
Adjacency list of vertex  3  :   1   5   7   9
Adjacency list of vertex  4  :   2   6
Adjacency list of vertex  5  :   3   6   7
Adjacency list of vertex  6  :   4   5   7   8
Adjacency list of vertex  7  :   2   3   5   6
Adjacency list of vertex  8  :   6
Adjacency list of vertex  9  :   0   1   2   3
Source node :  0
Length  k :  48
Result : YES

Source node :  0
Length  k :  51
Result : NO

Source node :  8
Length  k :  54
Result : YES``````
``````#    Ruby Program for
#    Find if there is a path of more than k length from a source
class AjlistNode
# Define the accessor and reader of class AjlistNode
attr_accessor :id, :length, :next
#  Vertices node key
def initialize(id, length)
#  Set value of node key
self.id = id
self.length = length
self.next = nil
end

end

class Vertices
# Define the accessor and reader of class Vertices
attr_accessor :data, :next
def initialize(data)
self.data = data
self.next = nil
end

end

class Graph
# Define the accessor and reader of class Graph
attr_accessor :size, :node
#  Number of Vertices
def initialize(size)
# set value
self.size = size
self.node = Array.new(size) {nil}
self.setData()
end

#  Set initial node value
def setData()
if (self.node == nil)
print("\nEmpty Graph", "\n")
else

index = 0
while (index < self.size)
self.node[index] = Vertices.new(index)
index += 1
end

end

end

#  Connect two nodes
def connect(start, last, length)
new_edge = AjlistNode.new(last, length)
if (self.node[start].next == nil)
self.node[start].next = new_edge
else

temp = self.node[start].next
while (temp.next != nil)
temp = temp.next
end

temp.next = new_edge
end

end

#  Add edge of two nodes
if (start >= 0 && start < self.size &&
last >= 0 && last < self.size && self.node != nil)
self.connect(start, last, length)
if (start == last)
#  Self looping situation
return
end

self.connect(last, start, length)
else

print("\nHere Something Wrong", "\n")
end

end

def printGraph()
if (self.size > 0 && self.node != nil)
index = 0
#  Print graph ajlist Node value
while (index < self.size)
print("\nAdjacency list of vertex ", index ," :")
temp = self.node[index].next
while (temp != nil)
print("  ", self.node[temp.id].data)
#  visit to next edge
temp = temp.next
end

index += 1
end

end

end

def isLengthGreaterThanK(index, visit, sum, k)
if (index < 0 || index >= self.size)
return false
end

if (visit[index] == true)
#  When node is already includes in current path
return false
end

if (sum > k)
#  When length sum is greater than k
return true
end

#  Here modified  the value of visited node
visit[index] = true
#  This is used to iterate nodes edges
temp = self.node[index].next
while (temp != nil)
if (self.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
#  Found path with length greater than k
return true
end

#  Visit to next edge
temp = temp.next
end

#  Reset the value of visited node status
visit[index] = false
return false
end

def checkPathGreaterThanK(source, k)
#  Set initial visited node status
visit = Array.new(self.size) {false}
print("\n Source node : ", source)
print("\n Length  k : ", k)
if (self.isLengthGreaterThanK(source, visit, 0, k))
print("\n Result : YES\n")
else

print("\n Result : NO\n")
end

end

end

def main()
#  10 implies the number of nodes in graph
g = Graph.new(10)
#  print graph element
g.printGraph()
#  Test A
source = 0
k = 48
g.checkPathGreaterThanK(source, k)
#  Test B
source = 0
k = 51
g.checkPathGreaterThanK(source, k)
#  Test C
source = 8
k = 54
g.checkPathGreaterThanK(source, k)
end

main()``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES
``````
``````/*
Scala Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode(
// Vertices node key
var id: Int,
var length: Int,
var next: AjlistNode)
{
def this(id: Int, length: Int)
{
// Set value of node key
this(id,length,null);
}
}
class Vertices(var data: Int,var next: AjlistNode)
{
def this(data: Int)
{
this(data,null);
}
}
class Graph(
// Number of Vertices
var size: Int,
var node: Array[Vertices])
{
def this(size: Int)
{
//set value
this(size,Array.fill[Vertices](size)(null));
this.setData();
}
// Set initial node value
def setData(): Unit = {
if (node == null)
{
println("\nEmpty Graph");
}
else
{
var index: Int = 0;
while (index < size)
{
node(index) = new Vertices(index);
index += 1;
}
}
}
// Connect two nodes
def connect(start: Int, last: Int, length: Int): Unit = {
var new_edge: AjlistNode = new AjlistNode(last, length);
if (node(start).next == null)
{
node(start).next = new_edge;
}
else
{
var temp: AjlistNode = node(start).next;
while (temp.next != null)
{
temp = temp.next;
}
temp.next = new_edge;
}
}
// Add edge of two nodes
def addEdge(start: Int, last: Int, length: Int): Unit = {
if (start >= 0 && start < size && last >= 0 &&
last < size && node != null)
{
connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
connect(last, start, length);
}
else
{
println("\nHere Something Wrong");
}
}
def printGraph(): Unit = {
if (size > 0 && node != null)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < size)
{
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode = node(index).next;
while (temp != null)
{
print("  " + node(temp.id).data);
// visit to next edge
temp = temp.next;
}
index += 1;
}
}
}
def isLengthGreaterThanK(
index: Int,
visit: Array[Boolean],
sum: Int, k: Int): Boolean = {
if (index < 0 || index >= this.size)
{
return false;
}
if (visit(index) == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit(index) = true;
// This is used to iterate nodes edges
var temp: AjlistNode = node(index).next;
while (temp != null)
{
if (isLengthGreaterThanK(
temp.id, visit,
sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit(index) = false;
return false;
}
def checkPathGreaterThanK(source: Int, k: Int): Unit = {
// Set initial visited node status
var visit: Array[Boolean] = Array.fill[Boolean](this.size)(false);
print("\n Source node : " + source);
print("\n Length  k : " + k);
if (isLengthGreaterThanK(source, visit, 0, k))
{
print("\n Result : YES\n");
}
else
{
print("\n Result : NO\n");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
// 10 implies the number of nodes in graph
var g: Graph = new Graph(10);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````
``````/*
Swift 4 Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
var id: Int;
var length: Int;
var next: AjlistNode? ;
init(_ id: Int, _ length: Int)
{
// Set value of node key
self.id = id;
self.length = length;
self.next = nil;
}
}
class Vertices
{
var data: Int;
var next: AjlistNode? ;
init(_ data: Int)
{
self.data = data;
self.next = nil;
}
}
class Graph
{
// Number of Vertices
var size: Int;
var node: [Vertices? ];
init(_ size: Int)
{
//set value
self.size = size;
self.node = Array(repeating: nil, count: size);
self.setData();
}
// Set initial node value
func setData()
{
var index: Int = 0;
while (index < self.size)
{
self.node[index] = Vertices(index);
index += 1;
}
}
// Connect two nodes
func connect(_ start: Int, _ last: Int, _ length: Int)
{
let new_edge: AjlistNode = AjlistNode(last, length);
if (self.node[start]!.next == nil)
{
self.node[start]!.next = new_edge;
}
else
{
var temp: AjlistNode? = self.node[start]!.next;
while (temp!.next  != nil)
{
temp = temp!.next;
}
temp!.next = new_edge;
}
}
// Add edge of two nodes
func addEdge(_ start: Int, _ last: Int, _ length: Int)
{
if (start >= 0 && start < self.size &&
last >= 0 && last < self.size && self.size > 0)
{
self.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
self.connect(last, start, length);
}
else
{
print("\nHere Something Wrong");
}
}
func printGraph()
{
if (self.size > 0)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < self.size)
{
index, " :", terminator: "");
var temp: AjlistNode? = self.node[index]!.next;
while (temp  != nil)
{
print("  ",
self.node[temp!.id]!.data, terminator: "");
// visit to next edge
temp = temp!.next;
}
index += 1;
}
}
}
func isLengthGreaterThanK(
_ index: Int, _ visit: inout[Bool],
_ sum: Int, _ k: Int) -> Bool
{
if (index < 0 || index >= self.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp: AjlistNode? = self.node[index]!.next;
while (temp  != nil)
{
if (self.isLengthGreaterThanK(
temp!.id, &visit, sum + (temp!.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp!.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
func checkPathGreaterThanK(_ source: Int, _ k: Int)
{
// Set initial visited node status
var visit: [Bool] = Array(repeating: false, count: self.size);
print("\n Source node : ", source, terminator: "");
print("\n Length  k : ", k, terminator: "");
if (self.isLengthGreaterThanK(source, &visit, 0, k))
{
print("\n Result : YES");
}
else
{
print("\n Result : NO");
}
}
}
func main()
{
// 10 implies the number of nodes in graph
let g: Graph = Graph(10);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}
main();``````

#### Output

``````Adjacency list of vertex  0  :   1   2   9
Adjacency list of vertex  1  :   0   3   9
Adjacency list of vertex  2  :   0   4   7   9
Adjacency list of vertex  3  :   1   5   7   9
Adjacency list of vertex  4  :   2   6
Adjacency list of vertex  5  :   3   6   7
Adjacency list of vertex  6  :   4   5   7   8
Adjacency list of vertex  7  :   2   3   5   6
Adjacency list of vertex  8  :   6
Adjacency list of vertex  9  :   0   1   2   3
Source node :  0
Length  k :  48
Result : YES

Source node :  0
Length  k :  51
Result : NO

Source node :  8
Length  k :  54
Result : YES``````
``````/*
Kotlin Program for
Find if there is a path of more than k length from a source
*/
class AjlistNode
{
// Vertices node key
var id: Int;
var length: Int;
var next: AjlistNode ? ;
constructor(id: Int, length: Int)
{
// Set value of node key
this.id = id;
this.length = length;
this.next = null;
}
}
class Vertices
{
var data: Int;
var next: AjlistNode ? ;
constructor(data: Int)
{
this.data = data;
this.next = null;
}
}
class Graph
{
// Number of Vertices
var size: Int;
var node: Array < Vertices?> ;
constructor(size: Int)
{
//set value
this.size = size;
this.node = Array(size)
{
null
};
this.setData();
}
// Set initial node value
fun setData(): Unit
{
if (this.size <= 0)
{
println("\nEmpty Graph");
}
else
{
var index: Int = 0;
while (index < this.size)
{
this.node[index] = Vertices(index);
index += 1;
}
}
}
// Connect two nodes
fun connect(start: Int, last: Int, length: Int): Unit
{
val new_edge: AjlistNode = AjlistNode(last, length);
if (this.node[start]?.next == null)
{
this.node[start]?.next = new_edge;
}
else
{
var temp: AjlistNode ? = this.node[start]!!.next;
while (temp?.next != null)
{
temp = temp.next;
}
temp!!.next = new_edge;
}
}
// Add edge of two nodes
fun addEdge(start: Int, last: Int, length: Int): Unit
{
if (start >= 0 && start < this.size && last >= 0 && last < this.size && this.size > 0)
{
this.connect(start, last, length);
if (start == last)
{
// Self looping situation
return;
}
this.connect(last, start, length);
}
else
{
println("\nHere Something Wrong");
}
}
fun printGraph(): Unit
{
if (this.size > 0)
{
var index: Int = 0;
// Print graph ajlist Node value
while (index < this.size)
{
print("\nAdjacency list of vertex " + index + " :");
var temp: AjlistNode ? = this.node[index]?.next;
while (temp != null)
{
print("  " + this.node[temp.id]?.data);
// visit to next edge
temp = temp.next;
}
index += 1;
}
}
}
fun isLengthGreaterThanK(index: Int, visit: Array < Boolean > , sum: Int, k: Int): Boolean
{
if (index < 0 || index >= this.size)
{
return false;
}
if (visit[index] == true)
{
// When node is already includes in current path
return false;
}
if (sum > k)
{
// When length sum is greater than k
return true;
}
// Here modified  the value of visited node
visit[index] = true;
// This is used to iterate nodes edges
var temp: AjlistNode ? = this.node[index]?.next;
while (temp != null)
{
if (this.isLengthGreaterThanK(
temp.id, visit, sum + (temp.length), k))
{
// Found path with length greater than k
return true;
}
// Visit to next edge
temp = temp.next;
}
// Reset the value of visited node status
visit[index] = false;
return false;
}
fun checkPathGreaterThanK(source: Int, k: Int): Unit
{
// Set initial visited node status
var visit: Array < Boolean > = Array(this.size)
{
false
};
print("\n Source node : " + source);
print("\n Length  k : " + k);
if (this.isLengthGreaterThanK(source, visit, 0, k))
{
print("\n Result : YES\n");
}
else
{
print("\n Result : NO\n");
}
}
}
fun main(args: Array < String > ): Unit
{
// 10 implies the number of nodes in graph
val g: Graph = Graph(10);
// print graph element
g.printGraph();
// Test A
var source: Int = 0;
var k: Int = 48;
g.checkPathGreaterThanK(source, k);
// Test B
source = 0;
k = 51;
g.checkPathGreaterThanK(source, k);
// Test C
source = 8;
k = 54;
g.checkPathGreaterThanK(source, k);
}``````

#### Output

``````Adjacency list of vertex 0 :  1  2  9
Adjacency list of vertex 1 :  0  3  9
Adjacency list of vertex 2 :  0  4  7  9
Adjacency list of vertex 3 :  1  5  7  9
Adjacency list of vertex 4 :  2  6
Adjacency list of vertex 5 :  3  6  7
Adjacency list of vertex 6 :  4  5  7  8
Adjacency list of vertex 7 :  2  3  5  6
Adjacency list of vertex 8 :  6
Adjacency list of vertex 9 :  0  1  2  3
Source node : 0
Length  k : 48
Result : YES

Source node : 0
Length  k : 51
Result : NO

Source node : 8
Length  k : 54
Result : YES``````

## Resultant Output Explanation

It performs a Depth-First Search (DFS) and checks if there is a path of length greater than 'k' starting from a given source node. The output explains the results for various test cases by printing "Result: YES" if a suitable path is found and "Result: NO" otherwise.

## Time Complexity

The time complexity of the algorithm depends on the number of vertices and edges in the graph. In the worst case, it's O(V + E), where 'V' is the number of vertices and 'E' is the number of edges. The algorithm visits each vertex once and explores all its outgoing edges, making it a linear-time operation.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.

### New Comment

Sergey Ivanov     331 Day ago
``````I am from Ukraine, I am 81 years old. I really like your work. Thank you! I'm writing a textbook for students on data structures and algorithms. I use your programs, supplement them with explanatory illustrations It would be nice if you developed a golang implementation of Dijkstra's algorithm. What do you recommend?
``````