Data Structures PJ3

소개글

연세대학교 데이타구조 플젝입니다. 만점받았습니다

목차

(1) Brief explanation of the problem
(2) Your view as to how it ties in with what we covered in class
(3) Discussion of your result
(4) Short explanation of your code
(5) Your code

본문내용

(1) Brief explanation of the problem
- The goal of this project is that I have to find a path through the maze by constructing an graph. And I should find a path by implementing a shortest path seatch on the graph by using algorithms code which is related to path searches such as Dijkstra`s algorithm, Prim`s algorithm or Kruskal`s algorithm. So through this project, I should understand them and make them.
(2) Your view as to how it ties in with what we covered in class
-Graph
The graph consists of a set of vertices and a set of edges. And each edge is a pair. So if the pair is ordered, then the graph is directed. In an undirected graph with edge(v,w) and w is adjacent to v and v is adjacent to w.(Our homework is related with undirected. ) A path in a graph is a sequence of vertices and the length of such a path is the number of edges on the path. A cycle in a directed graph is a path of length at least 1 such that w1=wn. This cycle is simple if the path is simple. For undirected graphs, we require that the edges be distinct. A greedy strategy is continually to select the edges in order of smallest weight and accept an edge if it does not cause a cycle.

<중 략>

for( j = 0 ; j < vertex_num ; j++){
min_cost=infinity; //맨 처음 거리의 최소값은 무한대로 지정.
for( i = 0; i < vertex_num ; i++){
if(known[i] == 0 && dist[i] < min_cost){ //아직 방문하지 않은 노드이고 거리가 최소거리보다 작으면
//다익스트라는 출발지에서 거리가 짧은거를 선태하는 알고리즘이기 때문
min_cost = dist[i]; //최소 거리를 바꿔주고
x = i; //x에 몇 번째(i)인지 저장
}
}
known[x] = 1; //x일때 거리가 최소가 되므로 x를 방문하고 이때 known을 1로 변환

for( k = 0 ; k < vertex_num ; k++){
new_dist = dist[x] + m[x][k] ; // 이전 노드의 거리 길이와 다음노드의 거리값을 저장
if(known[k] == 0 && new_dist < dist[k]){ //아직 방문하지 않은 노드이고
//이전노드와다음노드의최소값이 더 작으면
dist[k] = new_dist; //최소거리를 바꿔주고
v[k] = x; //최소거리들을 v배열에 저장, 이것은 나중에 path를 구할 떄 쓰기위하여 구현함.

참고 자료

없음