Dijkstra: Path Recovery
Problem
You are given a directed weighted graph. Find the shortest path from one given vertex to another.
Input
The first line contains three numbers: N, S and F (1≤N≤100, 1≤S, F≤N), where N – number of graph vertices, S – initial vertex, and F – final. In the next N lines, enter N numbers each, not exceeding 100, – graph adjacency matrix, where -1 means no edge between vertices, and any non-negative number – the presence of an edge of given weight. Zeros are written on the main diagonal of the matrix.
Output
It is required to display sequentially all the vertices of one (any) of the shortest paths, or one number -1 if there is no path between the specified vertices.
Examples
| # |
Input |
Output |
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |