Занятие 8. Справочник

static final int INF = Integer.MAX_VALUE;
static int n, s, np = 0;
static boolean[] used;
static int[] dist;
static int[] parent;
static int[][] graph;
staticintpath[];

n = in.nextInt();
s = in.nextInt() - 1;
f = in.nextInt() - 1;
graph = new int[n][n];
used = new boolean[n];
dist = new int[n];
parent = new int[n];
path = new int[n];
for (int i = 0; i < n; i++)
	for (int j = 0; j < n; j++)
		graph[i][j] = in.nextInt();
for (int i = 0; i < n; i++)
	dist[i] = INF;

static void dijkstra(int s) 
{
	parent[s] = -1;
	dist[s] = 0;
	for (int i = 0; i < n; i++) 
	{
		int v = -1;
		for (int j = 0; j < n; j++)
		{
			if (!used[j] && (v == -1 || dist[j] < dist[v]))
				v = j;
		used[v] = true;
		for (int j = 0; j < n; j++)
		{
			if (dist[v] + graph[v][j] < dist[j] &&
				graph[v][j] != 	-1) 
			{
				dist[j] = dist[v] + graph[v][j];
				parent[j] = v;
			}
		}
	}
}

static void recoverPath(int v) {
	if (v != s) recoverPath(parent[v]);
	path[np++] = v;
}