ダイクストラ法

 chat-gptにコーディングしてもらったダイクストラ

「クラスカルでパスファインダーを」ってリクエストしたら

ダイクストラを勧められた

クラスカルが作るのは経路でなくツリーなのだ

    参考動画

<script src="https://cdnjs.cloudflare.com/ajax/libs/p5.js/1.5.0/p5.js"></script>
<div id="p5canvas"></div>

<script>

class Graph {
  constructor() {
    this.vertices = [];
  }

  addVertex(x, y) {
    this.vertices.push({ x, y, edges: [] });
  }

  addEdge(source, destination, weight) {
    if (this.vertices[source] && this.vertices[destination]) {
      this.vertices[source].edges.push({ target: destination, weight });
      this.vertices[destination].edges.push({ target: source, weight });
    } else {
      throw new Error("Invalid vertex");
    }
  }

  calculateDistance(vertex1, vertex2) {
    const { x: x1, y: y1 } = this.vertices[vertex1];
    const { x: x2, y: y2 } = this.vertices[vertex2];
    return Math.hypot(x2 - x1, y2 - y1);
  }

  dijkstra(startVertex, endVertex) {
    const distances = Array(this.vertices.length).fill(Infinity);
    const visited = Array(this.vertices.length).fill(false);
    const previous = Array(this.vertices.length).fill(null);
    distances[startVertex] = 0;

    const queue = [{ vertex: startVertex, distance: 0 }];
    while (queue.length) {
      queue.sort((a, b) => a.distance - b.distance);
      const { vertex } = queue.shift();

      if (visited[vertex]) continue;
      visited[vertex] = true;

      if (vertex === endVertex) break;

      const neighbors = this.vertices[vertex].edges;
      neighbors.forEach(neighbor => {
        const newDistance = distances[vertex] + neighbor.weight;
        if (newDistance < distances[neighbor.target]) {
          distances[neighbor.target] = newDistance;
          previous[neighbor.target] = vertex;
          queue.push({ vertex: neighbor.target, distance: newDistance });
        }
      });
    }

    const path = [];
    let currentVertex = endVertex;
    while (currentVertex !== null) {
      path.unshift(currentVertex);
      currentVertex = previous[currentVertex];
    }
    return { distances, path };
  }

  printGraph() {
    for (let i = 0; i < this.vertices.length; i++) {
      const { x, y, edges } = this.vertices[i];
      console.log(`Vertex ${i} (${x}, ${y}) with edges:`);
      edges.forEach(edge => {
        console.log(`  -> Target: ${edge.target}, Weight: ${edge.weight}`);
      });
    }
  }
}

function getRandomInt(max) {
  return Math.floor(Math.random() * max);
}


// 使用例

let graph = new Graph();

const startVertex = 0;
const endVertex = 3;

let dijkRet;

const vtx=[50,200,350,500,125,275,425,125,275,425];
const vty=[150,150,150,150,75,75,75,225,225,225];


const edges=[
 [0,1,5],[1,2,5],[2,3,5],
 [4,5,5],[5,6,5],[7,8,5],[8,9,5],
 [0,4,5],[0,7,5],[1,4,5],[1,7,5],
 [1,5,5],[1,8,5],[2,5,5],[2,8,5],
 [2,6,5],[2,9,5],[3,6,5],[3,9,5],
 ];
 

function setup() {
  createCanvas(550, 500).parent("p5canvas");
  textSize(17);
  
  runDijkstra();
 }

 function runDijkstra(){ 
  graph=new Graph();
  for(let i=0;i<vtx.length;i++){
   graph.addVertex(vtx[i], vty[i]); 
  }

  for(let i=0;i<edges.length;i++){
   graph.addEdge(edges[i][0],edges[i][1],getRandomInt(10)+1); 
  }
   
  graph.printGraph();    
  dijkRet= graph.dijkstra(startVertex, endVertex);

  console.log(`Shortest Path from ${startVertex} to ${endVertex}: [${dijkRet.path.join(" -> ")}], Distance: ${dijkRet.distances[endVertex]}`);  
 }
  
 function mousePressed() {
  runDijkstra();
 }
 
 

 function draw() {
  background(100);
  
  stroke(255, 255, 155);
  strokeWeight(1);
  for(let i=0;i<graph.vertices.length;i++){
   fill(255);
   circle(graph.vertices[i].x,graph.vertices[i].y,15);
   for(let j=0;j<graph.vertices[i].edges.length;j++){
    let neiNum=graph.vertices[i].edges[j].target;
    
    if(neiNum>i){
     let x1=graph.vertices[i].x;
     let y1=graph.vertices[i].y;
     let x2=graph.vertices[neiNum].x;
     let y2=graph.vertices[neiNum].y;
     line(x1,y1,x2,y2);
    }
   }
  }
 
  for(let j=0;j<dijkRet.path.length-1;j++){
    let x1=graph.vertices[dijkRet.path[j]].x;
    let y1=graph.vertices[dijkRet.path[j]].y;
    let x2=graph.vertices[dijkRet.path[j+1]].x;
    let y2=graph.vertices[dijkRet.path[j+1]].y;
    fill(200,255,200);
    stroke(200,255,200);
    strokeWeight(5);
    line(x1,y1,x2,y2); 
  }
  
  
  for(let i=0;i<graph.vertices.length;i++){
   stroke(100);
   fill(100,255,100);
   text(i,graph.vertices[i].x,graph.vertices[i].y-10);
   for(let j=0;j<graph.vertices[i].edges.length;j++){
    let neiNum=graph.vertices[i].edges[j].target;    
    if(neiNum>i){
     let weit=graph.vertices[i].edges[j].weight;
     let x1=graph.vertices[i].x;
     let y1=graph.vertices[i].y;
     let x2=graph.vertices[neiNum].x;
     let y2=graph.vertices[neiNum].y;
     fill(240);
     text(weit,(x1+x2)/2,(y1+y2)/2);
    }
   }
  }
    
  noStroke(0);
  text("Shortest Path from  "+ startVertex+ "  to  " +endVertex+"  :",50,350);
  text("Distance:  "+dijkRet.distances[endVertex],50,370);
  text("[ "+dijkRet.path.join(" -> ")+" ]",50,400);
  text("When you click the mouse, it will recalculate.",50,480);

 }
</script>