8. Quick Boost with Graph | Learning F# Functional Data Structures and Algorithms

Finding the minimal path sum

The problem provides an 80 x 80 matrix in a text file, allowing traversal from the top left to the bottom right by only moving right and down.

As we discussed above, Dijkstra has one cost function which helps to find the shortest path from the source node to every other node by considering only the real cost (in contrast with A* heuristic). In order to solve the matrix problem, let's see how the graph implementation helps us.

First of all we will iterate through the matrix file and read the comma-delimited costs in the array. You can see the implementation in the following code snippet:

let weights = File.ReadAllLines("matrix.txt")
  |> Array.map(fun line -> line.Split(',') |> Array.map int32)
let matrixHeight = weights.Length;
let matrixWidth = weights.[0].Length;

As in the graph type described above, let's declare a node. A node consists of a list of coordinates (2D) for the matrix coordinates and the parent node, as well as the cost (weight).

type Node...

Tech Concepts

Programming languages

Tech Tools

Unlimited access to the largest independent learning library in tech of over 8,000 expert-authored tech books and videos.

Innovative learning tools, including AI book assistants, code context explainers, and text-to-speech.

50+ new titles added per month and exclusive early access to books as they are being written.

Learning F# Functional Data Structures and Algorithms

By : Adnan Masood

Learning F# Functional Data Structures and Algorithms

By: Adnan Masood

Overview of this book

Finding the minimal path sum

Learning F# Functional Data Structures and Algorithms

By : Adnan Masood

Learning F# Functional Data Structures and Algorithms

By: Adnan Masood

Overview of this book

Finding the minimal path sum

Confirmation

Buy this book with your credits?

Submit Your Feedback

Create a Free Account To Continue Reading

Sign in to activate your 7-day free access