Floyd-Warshall Algoritması

1interface Graph {
2  nodes: Map;
3  edges: GraphEdge[];
4}
5
6interface GraphEdge {
7  from: string;
8  to: string;
9  weight: number;
10}
11
12// Floyd-Warshall algorithm for all-pairs shortest paths
13function floydWarshall(graph: Graph): {
14  distances: Map>;
15  next: Map>;
16} {
17  const nodeIds = Array.from(graph.nodes.keys());
18  const distances = new Map>();
19  const next = new Map>();
20
21  // Initialize distance and next matrices
22  nodeIds.forEach(i => {
23    distances.set(i, new Map());
24    next.set(i, new Map());
25    
26    nodeIds.forEach(j => {
27      if (i === j) {
28        distances.get(i)!.set(j, 0);
29      } else {
30        distances.get(i)!.set(j, Infinity);
31      }
32      next.get(i)!.set(j, null);
33    });
34  });
35
36  // Set direct edge distances
37  graph.edges.forEach(edge => {
38    distances.get(edge.from)!.set(edge.to, edge.weight);
39    next.get(edge.from)!.set(edge.to, edge.to);
40  });
41
42  // Main Floyd-Warshall algorithm
43  nodeIds.forEach(k => {
44    nodeIds.forEach(i => {
45      nodeIds.forEach(j => {
46        const currentDistance = distances.get(i)!.get(j)!;
47        const newDistance = distances.get(i)!.get(k)! + distances.get(k)!.get(j)!;
48        
49        if (newDistance < currentDistance) {
50          distances.get(i)!.set(j, newDistance);
51          next.get(i)!.set(j, next.get(i)!.get(k));
52        }
53      });
54    });
55  });
56
57  return { distances, next };
58}
59
60// Reconstruct shortest path between two nodes
61function reconstructPath(
62  next: Map>,
63  start: string,
64  end: string
65): string[] {
66  if (next.get(start)!.get(end) === null) {
67    return []; // No path exists
68  }
69
70  const path: string[] = [start];
71  let current = start;
72
73  while (current !== end) {
74    current = next.get(current)!.get(end)!;
75    path.push(current);
76  }
77
78  return path;
79}
80
81// Usage example
82const graph: Graph = createExampleGraph();
83const result = floydWarshall(graph);
84const path = reconstructPath(result.next, '0', '3');
85console.log('Shortest path from 0 to 3:', path);
86console.log('Distance:', result.distances.get('0')!.get('3'));