dijkstra의 알고리즘을 윈도우에 구현하기 차트 컨트롤

Question

연결된 그래프의 최단 경로를 찾는 dijkstra의 모델을 구현하려고합니다. 내가 가지고있는 그래프는 버튼을 때 그래프에서 임의로 노드를 생성하는 그래프입니다.

1. 그래프가 연결되어 있는지 확인하거나 연결 한 경우
2. , 가장 짧은 경로를 찾는 한 세 가지의 다른 방법으로 결정하지 : 을 내가하고 싶은 무엇

   는 다음과 같습니다. 시작과 끝 노드 사이의 거리 별 최단 경로 b. 모서리 수에 따른 최단 경로 c. 모서리의 총중량에 따른 최단 경로 (여기에 우리가 원하는 것이 더 적음 ...)

몇 가지 다른 메모.

이 DataPoints는이 차트 컨트롤에서 임의로 생성되기 때문에 실제로 정점을 생성하는 Vertex 클래스가 없습니다. 저는 주변을 검색해 왔으며 대부분의 경로 찾기 함수가 정점 클래스를 사용한다는 것을 알았습니다. 그래서 기본적으로 내 목록은 차트 컨트롤에서 노드로 채워질 것입니다.

위의 두 가지 질문을 해결하는 방법에 대한 정보를 제공하는 사람이 있습니까?

//TODO: Change to a function with return bool. Void for purposes of testing at the moment. 
    public void isConnected() 
    { 

     List<DataPoint> ParentPoints = new List<DataPoint>(); 

     //Gather all the non data generator into the same point array 
     foreach (DataPoint pNonDG in chtGraph.Series[0].Points) 
     { 
      ParentPoints.Add(pNonDG); 
     } 
    } 

Answer 1

컴퓨팅 과학 그래프는 통계 또는 수학에서 만든 "차트"그래프와 다릅니다. 컴퓨터 과학 그래프는 일련의 "가장자리"를 통해 연결된 "노드"모음입니다.

노드는 가장자리를 통해 연결되어 있지만 연결되어있는 것은 아닙니다. 일부 가장자리는 단방향 연결 일 수 있습니다.

가장자리에는 종종 "가중치"또는 "비용"이 있습니다. 이것이 다이크 스트라 알고리즘이 유용 할 곳입니다. 이 비용을 사용하여 대상에 대한 최단 경로를 계산합니다.

우리가

class GraphNode { 
    List<GraphEdge> Edges = new List<GraphEdge>(); 
    public void AddEdge(GraphEdge edge) { 
     Edges.Add(edge); 
    } 
    //you get the idea, this should have much more 
    //it also manages edge connections 
} 

class GraphEdge { //this is a one way connection 
    GraphNode ConnectedTo = null; 
    //GraphNode ConnectedFrom = null; //if you uncomment this, it can be a two-way 
             //connection, but you will need more code to 
             //manage it 
    float Cost = 0f; 
    //you might consider adding a destructor that clears the pointers 
    //otherwise gc might have a hard time getting rid of the nodes 
} 

class Graph { 
    List<GraphNodes> Nodes = new List<GraphNodes>(); 
    //this class manages the nodes 
    //it also provides help for connecting nodes 
}