4853. The shortest path
The undirected graph is given. Find the
shortest path from vertex a to vertex b.
Input. The first line contains two integers n and m
(1 ≤ n ≤ 5 * 104, 1 ≤ m ≤ 105)
– the number of vertices and edges. The second line contains two integers a
and b – the starting and ending point correspondingly. Next m lines
describe the edges.
Output. If the path between a and b does not
exist, print -1. Otherwise print in the first line the length l of
the shortest path between these two vertices in number of edges, and in the
second line print l + 1 numbers – the vertices of this path.
|
Sample
input |
Sample
output |
|
4 5 1 4 1 3 3 2 2 4 2 1 2 3 |
2 1 2 4 |
SOLUTION
graphs – breadth first
search
Algorithm analysis
In this problem it is
necessary to implement breadth first search by constructing an array of shortest distances dist
and an array of ancestors parent from the source to all vertices. Since
the number of vertices is about 50000, the graph should be stored as an
adjacency list.
Example
Graph given in the sample,
has the form:
Algorithm realization
Declare an
adjacency list g for storing the graph, as well as additional arrays:
dist[i] stores the
shortest distance from source to vertex i, parent[i] stores the parent of vertex i
during the bfs.
#define MAX 50010
int used[MAX], dist[MAX], parent[MAX];
vector<vector<int> > g;
Function bfs
runs the breadth first search from the vertex start. The queue is
implemented as a local array q of size MAX (at any time, the number of
vertices in the queue will be no more than the number of vertices in the
graph). Head and Tail are pointers to the head and end of the
queue.
void bfs(int
start)
{
memset(used,0,sizeof(used));
memset(parent,-1,sizeof(parent));
memset(dist,-1,sizeof(dist));
dist[start] = 0;
int q[MAX],
Head = 0, Tail = 1;
q[Head] = start; used[start] = 1;
while(Head
< Tail)
{
int v =
q[Head++];
If there is an edge from v to to,
and the vertex to yet is not visited, then we to it ((v, to) is an edge of the tree
during the breadth first search).
for(int i = 0; i < g[v].size(); i++)
{
int to =
g[v][i];
if
(!used[to])
{
q[Tail++] = to;
used[to] = 1;
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
Using the parent
array parent, print the shortest path from the source to the vertex v.
Before each vertex, except for the initial one, print a space. The vertex v
is initial if parent [v] = -1.
void path(int
v)
{
if (v == -1) return;
path(parent[v]);
if (parent[v]
!= -1) printf(" ");
printf("%d",v);
}
The main part of
the program. Read the input
data.
scanf("%d %d",&n,&m);
scanf("%d %d",&a,&b);
g.resize(n+1);
while(scanf("%d
%d",&u,&v) == 2)
{
g[u].push_back(v);
g[v].push_back(u);
}
Run the breadth first search from the vertex x.
bfs(a);
If the vertex b is not reached
during the search (parent[b] is -1), then output -1. Otherwise, print
the value of the shortest distance to b and the
corresponding shortest path.
if (parent[b] == -1)
printf("-1\n");
else
{
printf("%d\n",dist[b]);
path(b);
printf("\n");
}
Algorithm realization – STL
#include <cstdio>
#include <vector>
#include <queue>
using namespace std;
int i, j, n, m, a, b, u,
v;
vector<int> dist, parent;
vector<vector<int> > g;
void bfs(int start)
{
parent = vector<int>(n + 1, -1);
dist = vector<int>(n + 1, -1);
dist[start] = 0;
queue<int> q;
q.push(start);
while (!q.empty())
{
int v = q.front(); q.pop();
for (int i = 0; i < g[v].size(); i++)
{
int to = g[v][i];
if (dist[to] == -1)
{
q.push(to);
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
int main(void)
{
scanf("%d %d", &n,
&m);
scanf("%d %d", &a,
&b);
g.resize(n
+ 1);
while (scanf("%d %d", &u, &v) == 2)
{
g[u].push_back(v);
g[v].push_back(u);
}
bfs(a);
if (parent[b] == -1)
printf("-1\n");
else
{
printf("%d\n", dist[b]);
vector<int> path(1, b);
while (parent[b] != -1)
{
b =
parent[b];
path.push_back(b);
}
for (i = path.size() - 1; i >= 0; i--)
printf("%d ", path[i]);
printf("\n");
}
return 0;
}
Java realization
import java.util.*;
public class Main
{
static ArrayList<Integer>[] g;
static int dist[], parent[];
static int n, m;
static void bfs(int start)
{
Arrays.fill(dist,-1);
dist[start] = 0;
Arrays.fill(parent,-1);
Queue<Integer> q = new LinkedList<Integer>();
q.add(start);
while(!q.isEmpty())
{
int v = q.poll();
for(int i = 0; i < g[v].size(); i++)
{
int to = g[v].get(i);
if (dist[to] == -1)
{
q.add(to);
dist[to] = dist[v] + 1;
parent[to] = v;
}
}
}
}
@SuppressWarnings("unchecked")
public static void main(String[] args)
{
Scanner con = new Scanner(System.in);
n = con.nextInt(); m = con.nextInt();
int a = con.nextInt();
int b = con.nextInt();
g = new ArrayList[n+1];
for(int i = 0; i <= n; i++)
g[i] = new ArrayList<Integer>();
dist = new int[n+1];
parent = new int[n+1];
for (int i = 0; i < m; i++)
{
int u = con.nextInt();
int v = con.nextInt();
g[u].add(v);
g[v].add(u);
}
bfs(a);
if (parent[b] == -1)
System.out.println("-1");
else
{
System.out.println(dist[b]);
Vector<Integer> path = new
Vector<Integer>();
path.add(b);
while (parent[b] != -1)
{
b = parent[b];
path.add(b);
}
for (int i = path.size() - 1; i >= 0; i--)
System.out.print(path.get(i) + " ");
System.out.println();
}
con.close();
}
}