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`

.

## Best Solution

You require to find the minimum spanning tree for it.

For directed graph according to wikipedia you can use this algorithm.