Given list of edges, find shortest path from source node to destination node in an unweighted graph.

Hint

The algorithm creates a map. Keys are starting points (source nodes) and values are list of points connected to the starting point. For the connections go both ways (like a two-way street), record connections in both directions in the map. For example, if "A" is connected to "B", also record that "B" is connected to "A".

Keep a list of places you've already been to track places visited. Also remember your path by keeping track of which place you came from to get to each place.

Start from your "source node." Put the starting place in a "queue.". Mark this place as "visited." Find all the places you can reach from here. For each place you can reach, if you haven't been there before, add this place to the "queue" list, and note down that you got to this place from the current place. Keep taking places from the "queue" list and exploring until you reach the place you want to find ("destination node").

Once you've reached the destination, follow the "came from" notes back to the starting place. This shows you the shortest path!

# Python implementation

V = 8
edges = [
  [0, 1], [0, 4], [1, 4], [1, 2], [2, 6], [3, 6], [3, 7], [5, 6]
]
source = 4
destination = 5

graph = [[] for _ in range(V)]

for edge in edges:
  graph[edge[0]].append(edge[1])
  graph[edge[1]].append(edge[0])

v = [False for _ in range(len(graph))]
p = [None for _ in range(len(graph))]
q = [source]
output = None

while(q):
  node = q.pop(0)
  v[node] = True
  for item in graph[node]:
    if not v[item]:
      p[item] = node
      q.append(item)

if v[destination]:
  output = [destination]
  
  c = destination
  while (p[c] != None):
    output.insert(0, p[c])
    c = p[c]

print(output)

// Javascript implementation

const edges = [
  [0, 1], [0, 4], [1, 4], [1, 2], [2, 6], [3, 6], [3, 7], [5, 6]
];
const source = 4;
const destination = 5;

const graph = [];

edges.forEach((item) => {
  if (graph[item[0]]) {
    graph[item[0]].push(item[1])
  } else {
    graph[item[0]] = [item[1]]
  }
  if (graph[item[1]]) {
    graph[item[1]].push(item[0])
  } else {
    graph[item[1]] = [item[0]]
  }
});

const v = Array(graph.length).fill(false);
const p = Array(graph.length).fill(null);
const q = [source];
let output = null;

while(q.length > 0) {
  const node = q.shift();
  v[node] = true;
  graph[node].forEach((item) => {
    if (!v[item]) {
      p[item] = node;
      q.push(item);
    }
  });
}

if (v[destination]) {
  output = [destination];
  
  let c = destination;
  while (p[c] !== null) {
    output.unshift(p[c]);
    c = p[c];
  }
}

console.log(output);

Find shortest path in an unweighted graph

Hint