Utilizing recursive methods for discovering routes in a two-dimensional matrix

Currently in the process of my A-level project, I am focused on the task of determining the maximum flow of a network using javascript.

My approach involves working with a 2D array where the values in the array represent distances between two points. For instance:

0 2 2 0
0 0 1 2
0 0 0 2
0 0 0 0

I believe a recursive technique is necessary to find a path. Below is some pseudocode assuming a 4x4 array, with 'a' at (0,0) and 'b' at (3,3).

function search(a,b)
  from a to b
    if element(i,j) != 0 then
      store value of element
      search(j,3)

My query pertains to if this is the correct structure for a depth-first search algorithm. I appreciate any assistance provided.

javascriptarraysrecursiontraversal

Answer №1

It is highly recommended to utilize the BFS algorithm for path finding. The Edmonds-Karp algorithm is a variant of the Ford-Fulkerson algorithm with a fixed path finding method, BFS, ensuring a worst-case time complexity of O(V * E^2), unlike DFS. Here, V represents the number of vertices and E represents the number of edges. However, if you choose to use DFS, it is crucial to ensure that the next node you visit in the loop has not been visited yet to avoid infinite recursion. You can achieve this by using a boolean array to keep track of visited nodes.

Answer №2

One effective method for achieving pathfinding is through the use of the floodfill algorithm, which can be implemented recursively as shown below:

function findPath(x, y, prevPoints)
{
 var prevPoints = prevPoints.concat([]); //create a copy of the points list to avoid reference issues in JavaScript

 if(grid[x][y].isExit) return prevPoints;
 grid[x][y].accessed = true;
 prevPoints.push([x, y]);

 var result;
 var cfr; //cellfillresult
 if(grid[x+1][y].isPath && !grid[x+1][y].accessed) cfr = findPath(x+1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x-1][y].isPath && !grid[x-1][y].accessed) cfr = findPath(x-1, y, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y+1].isPath && !grid[x][y+1].accessed) cfr = findPath(x, y+1, prevPoints);
 if(cfr != null) result = cfr;

 if(grid[x][y-1].isPath && !grid[x][y-1].accessed) cfr = findPath(x, y-1, prevPoints);
 if(cfr != null) result = cfr;

 return result;
}

var efficientPath = findPath(entranceX, entranceY, []);

Nevertheless, using this method on large grids can be inefficient, possibly resulting in a stack overflow. To address this, consider implementing a software stack instead.

In addition, it's important to note that this algorithm finds a working path but may not necessarily be the most optimal one. To improve efficiency, consider adding a way to track and evaluate the most efficient path.

Similar questions

If you have not found the answer to your question or you are interested in this topic, then look at other similar questions below or use the search

Clicking on the menu in mobile view will cause it to slide upward

I have implemented sticky.js on my website and it is working well. However, when I resize the browser to mobile view and click the main menu button, it goes up and I am unable to close it. I have to scroll up to see it again. How can I make it stick to the ...

javascriptjquerycssresponsive-design

What makes this effective in JavaScript?

While working on a project, I encountered the task of comparing coordinates in two arrays at the same index to see if they are identical. There are various methods to achieve this, but one particular approach piqued my interest. Why does it yield the expec ...

javascriptarraysfor-loop

Steps for effectively deleting browsing history on Ionic

While testing my app on Chrome browser, I encountered an issue with clearing old views and cache. This is the process I followed to sign out of my app: https://i.stack.imgur.com/EGgRx.png Upon clicking Log out, the following code is executed: Auth.$s ...

javascriptcordovaionic-framework

Unable to expand or collapse rows in ng-table

Looking to implement an expand and collapse feature for ng-table, where clicking on a row should expand it to show more detail. However, currently all rows expand on click. Any ideas on how to achieve this? Any assistance would be greatly appreciated, tha ...

javascripthtmlangularjs

Tips for posting images upon clicking a div instead of a submit button

I previously had a code that allowed users to click on the submit button and have the text inside a contenteditable div passed to upload.php using JQuery, inserted into a database, and immediately displayed. Now, I want to modify this code to also handle i ...

javascriptphpjqueryajaxupload

Retrieve the text input from the text field and display it as

Is there a way to display what users enter in a textfield when their accounts are not "Activated"? Here's an example: if(active == NULL);{ //I've attempted the following methods. //In this scenario, 'username' is the name of ...

javascriptphphtml

Ways to eliminate class from HTML code

Trying to detect if a navigational element has a specific class upon click. If it has the class, remove it; if not, add it. The goal is to display an active state on the dropdown button while the dropdown is open. The active state should be removed when a ...

javascripthtmljquerycss

"Trouble with props: List items not showing up after refreshing the page

I am facing an issue with my "Event Selector" component where it is not displaying the list items as expected. The component is supposed to create a button for each item in the 'lists' passed via props. Strangely, the items do not show up upon re ...

javascriptreactjsmaterial-uireact-props

Automatically trigger the expansion of all panels within Vuetify using code

I'm attempting to use Vuetify 2.3.5 to programmatically control the opening and closing of expansion panels. <v-expansion-panels accordion> <v-expansion-panel v-for="(item,i) in faqs" :key="i"> <div class ...

javascriptvue.jsvuetify.js

The error stating that document.getElementById(...) is null has occurred within RSForms due to a TypeError

Issue: When clicking on the form to continue, a TypeError: document.getElementById(...) is null error occurs. Can anyone help me fix this problem? When I click on the continue button, it calls the function submitForm. <script type="text/javascript"> ...

javascript

What is the method for displaying script commands within package.json files?

With a multitude of repositories, each one unique in its setup, I find myself constantly referencing the package.json file to double-check the scripts. "scripts": { "start": "npm run dev" "build:dev": "N ...

javascriptnode.jstypescriptnpm

Rotating Points in Three.js

I'm currently experimenting with a particle system project and I would like to incorporate a slight delay in the rotation of my Points Object in three.js. At the moment, I am using D3.js linear scale which results in a 1:1 rotation. This means that if ...

javascriptd3.jsthree.jsrotation

Loading time for page style can be slow when using Next Js

When the user opens or reloads the page, there is a delay in loading the style of the page. I am relatively new to working with next js and still learning the core abilities of the framework. This GIF illustrates the slow loading time when opening or relo ...

javascriptreactjswebfrontendnext.js

Tips for shrinking the circumference of a circle

Currently, I have a circular div that has been styled using CSS animations. My goal is to keep the size of the circle consistent when it moves to the bottom, but reduce its size when it bounces back to the top. I am uncertain if this can be achieved solely ...

javascriptjqueryhtmlcss

Adding a <tr> tag to an HTML table using JQuery and AJAX in the context of Django framework step by step

I am currently navigating the world of Javascript, Jquery, and Ajax requests and I'm encountering a challenge with how my scripts are executing. My homepage contains a lengthy list of items (over 1200) that need to be displayed. Previously, I loaded ...

javascripthtmljquerydjangoajax

Issue with ReactJS: onChange event does not function properly when value is changed using jQuery

This is the reactjs code I am working with: <input name="date" id="date" value={this.state.listManage.date} onChange={this.handleForm} type="text" /> When I manually type in the input field, the onChange function works ...

javascriptjqueryreactjs

JavaScript code to retrieve an image from an <img> tag's source URL that only allows a single request and is tainted due to cross-origin restrictions

I have an image displayed in the HTML DOM. https://i.stack.imgur.com/oRgvF.png This particular image (the one with a green border) is contained within an img tag and has a URL as its source. I attempted to fetch this image using the fetch method, but enc ...

javascriptpythonhtmlseleniumcanvas

Tips on setting up a self-start event or alert in ASP.NET

I am trying to figure out how to trigger an alert for the user once a specific time has been reached. The challenge is that it cannot be initiated by a button click event or any other action. I want the alert to be displayed even if the user is on a diff ...

c#javascriptjqueryasp.net

Is it possible to generate a "pop-up" window upon clicking on the register button?

As a backend programmer, I'm looking to create a popup window that appears in front of the current window when users click "register", eliminating the need for redirection to another page. I believe you understand the concept. How can I achieve this? ...

javascriptjqueryajaxfrontend

Is there a way to extract an icon from an object or array?

Currently, I am facing challenges in extracting an icon from either an object or an array for a project I am working on. My approach involves storing the icon in a variable and passing it as a prop to another component. However, the functionality is not wo ...

javascriptreactjsopenweathermap