그림dijkstra 알고리즘 [데이터 구조 실천 보고서]

데이터 구조 실험 보고서
실험 명칭: 실험 7 도 dijkstra 알고리즘
학 번: * * *
이름: gnosed
시험 날짜: 2017.12.23
 
실험 목적
최 단 경 로 를 구 하 는 Dijkstra 알고리즘 파악
 
2. 실험의 구체 적 인 내용
1. 실험 문제 1:
(1) 제목
프로그램 작성, Dijkstra 알고리즘 으로 그림 의 최 단 경로 구하 기
(2) 분석
메모리 구조:

그림 은 인접 행렬 로 관계 행렬 의 대각선 초기 값 을 0 으로 표시 한다.

배열 dist []: dist [i] 는 최종 적 으로 Vo 에서 Vi 까지 의 최 단 경로 와 최 단 경로 에서 Vi 의 전구 정점 (계산 과정 은 거리 값 이 고 조정 할 수 있 습 니 다) 을 저장 합 니 다.

설명:

dist 는 집합 U 와 V 두 부분 으로 나 눌 수 있 습 니 다. U 는 Vo 에서 한 정점 까지 가장 짧 은 경로 의 모든 정점 을 말 합 니 다. V 는 가장 짧 은 경 로 를 정 하지 않 은 정점 집합 을 말 합 니 다.

dist 를 초기 화 할 때 집합 U 는 Vo 만 있 고 해당 하 는 거리 값 은 0 입 니 다.집합 V 에서 Vi 의 거리 값 은 변 (Vo, Vi) 의 권리 이 고 만약 에 Vo 와 Vi 사이 에 직접적인 변 이 없 으 면 Vi 의 거리 값 은 무한대 (여 기 는 1000) 이다.

알고리즘 프로 세 스:
1) 집합 V 에서 거리 값 이 가장 작은 정점 Vmin 을 선택 하여 집합 U 에 추가 (대각선 원소 값 을 1 로 변경 하여 표시 가능)
2) 위 에서 선택 한 Vmin 을 U 에 놓 을 때 만약 에 Vmin 이 Vo 가 다른 정점 V [i] 의 가장 짧 은 경로 에 있 는 정점 일 수 있 기 때문에 dist [i] 의 거리 값 이 줄 어 들 기 때문에 이때 min 값 에 따라 집합 V 의 각 정점 의 거리 값 을 조정 해 야 합 니 다. 만약 에 Vo 에서 Vi 까지 의 거리 값 이 원래 의 거리 값 보다 작 으 면 Vi 의 거리 값 dist [i]. length 를 수정 해 야 합 니 다. 그렇지 않 으 면 수정 하지 않 습 니 다.
3) 중복 1) 2) 보 에서 도달 할 수 있 는 모든 정점 이 집합 U 에 들 어 갈 때 까지 한다.
(3) 실험 코드
원본 코드:

#include 
#include 
#define Vextype int
#define Adjtype int
#define VN 6
#define MAX 1000
using namespace std;

struct GraphMatrix
{
    Vextype vex[VN][VN];
    Adjtype arc[VN][VN];
};
typedef struct{
    Adjtype length;//shortest path
    int prevex;//Vi     
}Path;
Path dist[VN];
void init(GraphMatrix *pgraph,Path *dist)
{
    dist[0].length=dist[0].prevex=0;
    pgraph->arc[0][0]=1;//          U， 1   U 
    for(int i=1;iarc[0][i];
        if(dist[i].length!=MAX) dist[i].prevex=0;
        else dist[i].prevex=-1;
    }
}
void dijkstra(GraphMatrix *pgraph,Path *dist)
{
    init(pgraph,dist);//   ，U   Vo
    Adjtype minw;
    int mv;
    for(int i=1;iarc[j][j]!=1 && minw>dist[j].length){
                minw=dist[j].length; mv=j;
            }
        if(mv==0)    break;//Vo V-U      ，  
        pgraph->arc[mv][mv]=1;//  mv  U
        for(int i=1;iarc[i][i]!=1&&
               dist[i].length>dist[mv].length+pgraph->arc[mv][i]){
                   dist[i].prevex=mv;
                    dist[i].length=dist[mv].length+pgraph->arc[mv][i];
               }
        }
    }
}

int main()
{
    GraphMatrix *G=new struct GraphMatrix;
    for(int i=0;i>G->arc[i][j];
    dijkstra(G,dist);
    cout<>en;
    k=en;
    cout< Path;
    while(1){
        Path.push(dist[k].prevex);
        k=dist[k].prevex;
        if(!k) break;
    }
    while(!Path.empty()){
        cout<";
        Path.pop();
    }
    cout<

Input

0 50 101000 45 1000
1000 0 15 1000 5 1000
20 1000 0 15 1000 1000
1000 20 1000 0 35 1000
1000 1000 1000 30 0 1000
1000 1000 1000 3 1000 0

Output:

   0，     :3
      :25
  :0->2->3