R – the shortest path in cycle directed Graph

Getting the name of the file without the extension:

import os
print(os.path.splitext("/path/to/some/file.txt")[0])

Prints:

/path/to/some/file

Documentation for os.path.splitext.

Important Note: If the filename has multiple dots, only the extension after the last one is removed. For example:

import os
print(os.path.splitext("/path/to/some/file.txt.zip.asc")[0])

Prints:

/path/to/some/file.txt.zip

See other answers below if you need to handle that case.

It is a simple dynamic programming algorithm.

Let us assume that we want to go from vertex x to vertex y.

Make a table D[.,.], where D[v,k] is the cost of the shortest path of length k from the starting vertex x to the vertex v.

Initially D[x,1] = 0. Set D[v,1] = infinity for all v != x.
For k=2 to n:
  D[v,k] = min_u D[u,k-1] + wt(u,v), where we assume that wt(u,v) is infinite for missing edges. 
  P[v,k] = the u that gave us the above minimum.

The length of the shortest path will then be stored in D[y,n].

If we have a graph with fewer edges (sparse graph), we can do this efficiently by only searching over the u that v is connected to. This can be done optimally with an array of adjacency lists.

To recover the shortest path:

Path = empty list
v = y
For k= n downto 1:
  Path.append(v)
  v = P[v,k]
Path.append(x)
Path.reverse()

The last node is y. The node before that is P[y,n]. We can keep following backwards, and we will eventually arrive at P[v,2] = x for some v.