Looking for a ML algorithm to predict a path based on millions of data

I have a dataset with following data format:

3 - a - b - c - d - ikd

a - c - 3 - dk - 2 - l2i

Each row represents a path from start to end. Let's take the first row as an example. The start point is 3 and the endpoint is ikd. I have millions of rows like that. And each row may have a different length. What I want to do is let users input a path with the above format and I predict a new path based on the existent dataset. The idea is to find the closest path for each user. Each node on the path may have a weight to indicate how important this node is. So the closest path should respect this weight.

Is there any ML algorithm for this kind of problem? I am new to ML so I need some guidance on solving this problem.

EDIT: There is no specific meaning for the type of each node, like number, letter, etc. All these nodes are of type string and the user's input is from an existent string list.