1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function shortestPath(graph, startVertex, endVertex) {
  // If start and end are the same, return an empty path
  if (startVertex === endVertex) {
    return { distance: 0, path: [startVertex] };
  }
  
  // Set to keep track of visited vertices
  const visited = new Set();
  
  // Queue for BFS, storing [vertex, distance, path]
  const queue = [[startVertex, 0, [startVertex]]];
  
  // Mark the start vertex as visited
  visited.add(startVertex);
  
  // While there are vertices in the queue
  while (queue.length > 0) {
    // Dequeue a vertex from the queue
    const [currentVertex, distance, path] = queue.shift();
    
    // Get all adjacent vertices of the dequeued vertex
    for (const neighbor of graph[currentVertex]) {
      // If this adjacent vertex is the destination, we've found the shortest path
      if (neighbor === endVertex) {
        return {
          distance: distance + 1,
          path: [...path, neighbor]
        };
      }
      
      // If this adjacent vertex has not been visited, mark it as visited and enqueue it
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push([neighbor, distance + 1, [...path, neighbor]]);
      }
    }
  }
  
  // If we reach here, there is no path from start to end
  return { distance: -1, path: [] };
}
 
// Example usage:
const graph = {
  'A': ['B', 'C'],
  'B': ['A', 'D', 'E'],
  'C': ['A', 'F'],
  'D': ['B'],
  'E': ['B', 'F'],
  'F': ['C', 'E']
};
 
const result = shortestPath(graph, 'A', 'F');
console.log("Shortest distance:", result.distance); // Output: 2
console.log("Shortest path:", result.path); // Output: ['A', 'C', 'F']

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
function wordLadder(beginWord, endWord, wordList) {
  // If endWord is not in wordList, return 0
  if (!wordList.includes(endWord)) {
    return 0;
  }
  
  // Convert wordList to a Set for O(1) lookups
  const wordSet = new Set(wordList);
  
  // Queue for BFS, storing [word, distance]
  const queue = [[beginWord, 1]];
  
  // Set to keep track of visited words
  const visited = new Set([beginWord]);
  
  // While there are words in the queue
  while (queue.length > 0) {
    // Dequeue a word from the queue
    const [currentWord, distance] = queue.shift();
    
    // If we've reached the end word, return the distance
    if (currentWord === endWord) {
      return distance;
    }
    
    // Try changing each character of the current word
    for (let i = 0; i < currentWord.length; i++) {
      // Try all possible characters
      for (let j = 0; j < 26; j++) {
        // Generate a new word by changing one character
        const newChar = String.fromCharCode(97 + j); // 'a' to 'z'
        const newWord = currentWord.slice(0, i) + newChar + currentWord.slice(i + 1);
        
        // If the new word is in the word list and hasn't been visited
        if (wordSet.has(newWord) && !visited.has(newWord)) {
          // Mark it as visited and enqueue it
          visited.add(newWord);
          queue.push([newWord, distance + 1]);
        }
      }
    }
  }
  
  // If we reach here, there is no transformation sequence
  return 0;
}
 
// Example usage:
const beginWord = "hit";
const endWord = "cog";
const wordList = ["hot", "dot", "dog", "lot", "log", "cog"];
 
const result = wordLadder(beginWord, endWord, wordList);
console.log("Shortest transformation sequence length:", result); // Output: 5
// The transformation sequence is: "hit" -> "hot" -> "dot" -> "dog" -> "cog"