Dijkstras 알고리즘 (C#

Question

)

Dijkstras alg를 처음부터 사용하는 차트 컨트롤을 작성합니다. 나는이 알고리즘을 이해하려고 인터넷을 샅샅이 조사했다. 나는 그것을 마침내 이해한다고 생각하지만 내 코드가 제대로 작동하지 않습니다. 누군가를 바라보며 이것에 대해 엿볼 수있을 것입니다. 그리고 그들이 그 거래가 무엇인지 알 수 있는지 알게 될 것입니다 ...

나는 이것이 모든 것이 필요할 것 같은 3 가지 방법으로 붙여 넣을 것입니다.

처음에는 내 자신의 버텍스 데이터 유형을 만들었다 고 말할 것입니다. 노드의 ID, X와 Y, 상태 문자열, 그리고 정점 데이터 유형 인 부모와 정수의 거리를 포함합니다.

//function to populate lists with all the vertices on the graph 
    private List<Vertex> getNodes() 
    { 
     myVertices.Clear(); 
     //get all non-dg nodes in list 
     for (int i = 0; i < chtGraph.Series[0].Points.Count; i++) 
     { 
      Vertex vertice = new Vertex(chtGraph.Series[0].Points[i]["ID"], (float)chtGraph.Series[0].Points[i].XValue, (float)chtGraph.Series[0].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[0].Points[i].Label), double.PositiveInfinity, null); 
      myVertices.Insert(i, vertice); 
     } 

     //get all dg nodes in list 
     for (int i = 0; i < chtGraph.Series[1].Points.Count; i++) 
     { 
      Vertex vertice = new Vertex(chtGraph.Series[1].Points[i]["ID"], (float)chtGraph.Series[1].Points[i].XValue, (float)chtGraph.Series[1].Points[i].YValues[0], "UNVISITED", Convert.ToInt32(chtGraph.Series[1].Points[i].Label), double.PositiveInfinity, null); 
      myVertices.Insert(i, vertice); 
     } 
     return myVertices; 
    } 

    //function to return to a list all the adjacents for a specified node. Excludes parent node 
    private List<Vertex> checkAdjacents(Vertex node, int intTransPower) 
    { 
     List<Vertex> Adjacents = new List<Vertex>(); 
     int distance; 

     for (int i = 0; i < myVertices.Count; i++) 
     { 
      if (node.id != myVertices[i].id) 
      { 
       distance = calcDistance(node.x, node.y, myVertices[i].x, myVertices[i].y); 

       if (distance <= intTransPower) 
       { 
        if (rdbTotalLength.Checked) 
        { 
         myVertices[i].distance = distance; 
        } 
        else if (rdbPathEnergy.Checked) 
        { 
         myVertices[i].distance = getCost(node, myVertices[i]); 
        } 
        else 
        { 
         myVertices[i].distance = 1; 
        } 

        myVertices[i].parent = node; 
        Adjacents.Add(myVertices[i]); 

        foreach (Vertex p in openList) 
        { 
         if (myVertices[i].id == p.id) 
         { 
          p.distance = myVertices[i].distance; 
          p.parent = myVertices[i].parent; 
         } 
        } 
       } 
      } 
     } 

     return Adjacents; 

    } 

여기 dijkstras ....입니다. 현재 제대로 작동하지 않고 있으며 그 사실을 알 수 없습니다.

private void dijkstra(Vertex start, Vertex end) 
    { 

     openList.Clear(); 

     //populate two lists with all the nodes in the graph 
     openList = getNodes(); 
     myVertices = getNodes(); 

     //adjacents list for each vertex visited 
     List<Vertex> adjacents = new List<Vertex>(); 

     //final list that is populated with the final path of vertices 
     List<Edge> shortestPath = new List<Edge>(); 

     //used in calculating adjacent nodes. If distance is greater than transpower, then nodes are not connected 
     int intTransPower = Convert.ToInt32(txtTransPower.Text); 

     //set current vertex as the starting node 
     Vertex current = start; 

     //set initially to false 
     bool pathFound = false; 

     //find the starting node from the list of all vertices. Set it's distance to 0 
     foreach (Vertex p in openList) 
     { 
      if (p.id == current.id) 
      { 
       p.status = current.status; 
       p.distance = 0; 
      } 
     } 
     foreach (Vertex p in myVertices) 
     { 
      if (p.id == current.id) 
      { 
       p.status = current.status; 
       p.distance = 0; 
      } 
     } 

     //reorder the list to bring the starting node to the first element 
     openList = openList.OrderBy(h => h.distance).ToList(); 

     //openList.Add(current); 
     //this.insert(openList, current, true); 

     // Repeat while the openlist is not empty and you haven't reached the end 
     while (openList.Count > 0) 
     { 
      //remove node at element 0. Sorted by smallest distance so it always gets removed first 
      current = openList[0]; 
      openList.RemoveAt(0); 

      //if the current node = the ending node, then we have found the path. Break loop and build the final path. 
      if (current.id == end.id) 
      { 
       pathFound = true; 
       break; 
      } 

      //collect up all the adjacent nodes for the current vertex 
      //does NOT include the current vertex we are on 
      adjacents = checkAdjacents(current, intTransPower); 

      foreach (Vertex v in adjacents) 
      { 
       float alt = (float)current.distance + calcDistance(current.x, current.y, v.x, v.y); 
       Convert.ToInt32(alt); 

       if (alt < v.distance) 
       { 
        v.distance = alt; 
        v.parent = current; 
        for (int i = 0; i < openList.Count; i++) 
        { 
         if (v.id == openList[i].id) 
         { 
          openList[i].distance = alt; 
          openList[i].parent = current; 
         } 
        } 
       } 

      } 
      openList = openList.OrderBy(h => h.distance).ToList(); 
     } 

     if (pathFound) 
     { 
      // collect path 
      this.foundPath.Clear(); 
      Vertex last = current; 
      while (current != start && current != null) 
      { 
       this.foundPath.Add(current); 
       if (current.parent == last) 
        break; 
       last = current; 
       current = current.parent; 
      } 
      this.foundPath.Add(current); 
     } 

    } 

Answer 1

나는이 방법을 가지고 있지만, 그것은 더 큰 구현을위한 일부입니다

public static IDigraph DijkstrasAlgorithm(IDigraph g, int s) 
     { 
      //Collect number of vertices 
      int num1 = g.NumberOfVertices; 

      //create an array for vertices 
      Entry[] entryArray1 = new Graphos.Algorithms.Entry[num1]; 

      //for each vertice create new instance for entry of edges 
      for (int num2 = 0; num2 < num1; num2++) 
      { 
       entryArray1[num2] = new Graphos.Algorithms.Entry(false, 0x7fffffff, 0x7fffffff); 
      } 
      //set vertice origin with distance 0. 
      entryArray1[s].distance = 0; 

      //create a list for edges 
      PriorityQueue queue1 = new BinaryHeap(g.NumberOfEdges); 

      //create initial nodes in edges list 
      queue1.Enqueue(new Association(0, g.GetVertex(s))); 

      //while list is not empty 
      while (!queue1.IsEmpty) 
      { 
       //creates an association 
       Association association1 = (Association)queue1.DequeueMin(); 

       //attributes the vertice 
       IVertex vertex1 = (IVertex)association1.Value; 

       //if connection is known 
       if (!entryArray1[vertex1.Number].known) 
       { 
        //checks as known 
        entryArray1[vertex1.Number].known = true; 

        //foreach edge founded 
        foreach (Edge edge1 in vertex1.EmanatingEdges) 
        { 
         //creates the vertex that is being used 
         IVertex vertex2 = edge1.MateOf(vertex1); 

         //catches the weight since vertice in link 
         int num3 = entryArray1[vertex1.Number].distance + ((int)edge1.Weight); 

         //se o peso da ponte for menor que o peso maximo 
         if (entryArray1[vertex2.Number].distance > num3) 
         { 
          //Peso maximo é atualizado para o peso da ponte 
          entryArray1[vertex2.Number].distance = num3; 

          //Define o vértice vizinho 
          entryArray1[vertex2.Number].predecessor = vertex1.Number; 

          //adiciona o vértice com seu vizinho e o peso entre eles na lista 
          queue1.Enqueue(new Association(num3, vertex2)); 
         } 
        } 
       } 
      } 
      //Á este ponto, todas as associações foram feitas 

      //Cria o objeto grafo como uma lista baseado no numero de vertices 
      IDigraph digraph1 = new DigraphAsLists(num1); 

      //Para cada vértice 
      for (int num4 = 0; num4 < num1; num4++) 
      { 
       //adiciona o vertice da lista no grafo 
       digraph1.AddVertex(num4, entryArray1[num4].distance); 
      } 

      //para cada vertice 
      for (int num5 = 0; num5 < num1; num5++) 
      { 
       //Se não for o ponto de origem 
       if (num5 != s) 
       { 
        //adiciona a aresta(origem,destino baseado no vizinho) 
        digraph1.AddEdge(num5, entryArray1[num5].predecessor); 
       } 
      } 
      //retorna o grafo 
      return digraph1; 
     } 

당신이를 표시 할 http://www.graphviz.org/을 사용할 수 있습니다 aswell 당신이 단위 테스트를 쓰기 시작한다