acm, 기본 그래 픽 알고리즘 및 해석

도 론 기본 알고리즘 은 사실 6 개, 2 개의 생 성 트 리, 4 개의 최 단 경로 이다.
 
전제 가 된 BFS 알고리즘 은 전체 그림 을 명시 적 으로 구축 하지 않 고 이웃 을 찾 을 때마다 도착 하거나 방문 이 끝나 면 종료 할 수 있다 는 장점 이 있 습 니 다.일반적으로 최 단 로 만 구 하 는 데 쓰 인 다.
기술: 배열 을 설정 하여 각 점 의 전구 점 을 기록 합 니 다.
그러나 DFS 로 서 는 전체 그림 을 명시 적 으로 구축 해 야 한다. 되 돌 릴 때 는 이전 지점 이나 다른 방식 으로 도착 하기 때문이다.실행 가능 한 경로 의 총 수 를 구 하 는 데 사용 합 니 다.
기교: 강력 한 가지치기.....
--------------------------------------------------------------------------------------------------------------------------------------------------
prim
 
알고리즘 핵심 사상: 집합 론의 관점 에서 볼 때 이 나무 에서 가장 가 까 운 점 을 계속 귀 약 하 는 것 이다.
weight[n]  이 집합 에서 각 점 (i) 까지 의 최 단 거 리 를 기록 합 니 다.
  adjex[n]  이 집합 에서 어느 점 에서 각 점 (i) 까지 의 최 단 거 리 를 기록 합 니까?
    visit[n]  어떤 점 이 그 집합 에 속 하 는 지 기록 하 라.
 

#include 
#include 
#define N 401
int state[N][N];
int maps [N][N];


int solve(int n)
{
	int weight[N];
	int adjex[N];
	int visit[N];
	int i,j,k;
	int minnum,ans;
	ans=0;
	for(i=0;iweight[j] && visit[j] == 0)
				minnum=weight[j],k=j;
		visit[k]=1;
		ans+=minnum;
		for(j=1;j

 
Kruskal
핵심 사상: 가장 짧 은 변 으로 생 성 나 무 를 구축 하고 회 로 를 피한다.
집합 을 사용 하여 한 변 의 두 점 이 같은 집합 에 있 는 지 빠르게 조회 하여 회 로 를 피한다.

/*
   ，                       
       
*/
void kruskal (edgeset ge, int n, int e)
// ge              
{ 
int set[MAXE], v1, v2, i, j;
for (i=1;i<=n;i++)
set[i]=0;　 　//  set        
i=1;　// i            ，   1
j=1;　// j  ge    ，    1
while (j

주: 그리고 집합 을 찾 으 면 경 로 를 압축 하여 조회 할 때마다 되 돌려 주 고 조회 시간 을 O (1) 로 돌려 줍 니 다.
 
 
Dijkstra
매번 그림 의 노드 로 모든 경 로 를 업데이트 하여 최 단 경로 의 목적 을 달성 합 니 다.
1. n 회 반복
2. 그래서 d [] 노드 에서 최소 x 찾기
3. 이 점 x 표시
4. 이 지점 에서 출발 하여 d [y] = min {d [y], d [x] + w [x] [y]} 을 업데이트 합 니 다.

void Dijkstra(){     
       int k;
    for(int i=1;i<=n;i++)      
        dis[i] = map[1][i];        
    for(int i=1;i dis[j] ){        
                tmin = dis[j];
                k = j;
            }
            used[k] = 1;      
        for(int j=1;j<=n;j++)       
            if( !used[j] &&dis[k] + map[k][j] < dis[j] )  //         ，          
                dis[j] = dis[k] + map[k][j];     
     }     
     printf("%d",dis[n]);
} /*  1 N    ,dis[i]    i            By Ping*/
//          ，          ，      

 
Floyd
업 데 이 트 된 중간 노드 k 를 사용 하여 가장 바깥쪽 에 있 습 니 다.(맨 안쪽 에 방법 을 어 겼 습 니 다. 한 노드 로 모든 경 로 를 업데이트 합 니 다)
마이너스 변 의 그림 을 가지 고 계산 할 수 있다.
임의의 두 점 (i, j) 사이 에 매번 하나의 노드 를 사용 하여 모든 경 로 를 업데이트 합 니 다.동시에 우 리 는 임의의 두 점 사이 의 최 단 거 리 는 최대 n - 1 개의 결점 을 거 친 다 는 것 을 안다
이렇게 되면 특정 두 가지 점 에 가입 하 는 점 의 순 서 는 중요 하지 않다.
1. 더 이상 두 가 지 를 원 하지 않 는 길, 상관 없어
2. 두 점 과 직접적 으로 연결 되 어 간접 적 으로 연결 되 어 우리 의 사고 에 부합된다.
3. 가장 중요 하 다. 순서 가 없 으 면 중간 하나 부터 시작 하면 어 떡 하지?
중간 점 이 라면 그 와 연 결 된 점 간 의 가장 짧 은 경 로 를 업데이트 할 것 이다. 그러면 다음 중간 점 에 도움 이 되 고 '중간 길' 을 먼저 닦 은 셈 이다.

//d[i][j]     i j        
// path[i][j]     i j      j       
//d[i][j]     i j        
void Floyd(int num,int **path,int**d,int **a)


{
    int i,j,k;
    for(i=0;id[i][k]+d[k][j])// i j        
                {
                    d[i][j]=d[i][k]+d[k][j];
                    path[i][j]=path[i][k];
                }
}

 
Bellman-Ford
이전의 가장 짧 은 경 로 를 구 하 는 것 은 그림 에 마이너스 변 이 없 기 때문에 이 알고리즘 은 마이너스 변 이 있 는 그림 의 가장 짧 은 경 로 를 구 할 수 있다.
각 변 을 이완 시 키 고 매번 이완 시 키 면 적어도 하나의 도착 점 을 증가 시 킬 수 있 기 때문에 외부 순환 은 v - 1 회 까지 이다.
디 제 스 트 라 와 다른 점 은 디 제 스 트 라 는 매번 하나의 점 을 사용 하여 업 데 이 트 를 한 후에 사용 하지 않 고 베 르 만 의 모든 변 을 매번 사용 한 다 는 것 이다.
디 제 스 트 라 는 매번 찾 은 최 단 로 의 집합 에서 찾 지 못 한 집합 으로 연결 되 는 길 을 찾 아 내부 의 점 을 모 으 는 최 단 로 를 다시 계산 하지 않 는 다.
설명:

dijkstra      ，             （dmin），                   （d[i] 
  
 
 
  
    ：
 
  
   -             ，         ，                     ，       。      ，                    ，               。   ，                          ，             ；    -                 ， |V | − 1 ，   |V |       。       ，                   ，                。          -                     。
 
  
   -         O（|V|·|E|) ，|V| |E|          ）。
 
  
 
 
  
    ：
 
  
#include 
using namespace std;
const int maxnum = 100;
const int maxint = 99999;
 
//  ，
typedef struct Edge{
    int u, v;    //   ，  
    int weight;  //     
}Edge;
 
Edge edge[maxnum];     //      
int  dist[maxnum];     //          
 
int nodenum, edgenum, source;    //    ，  ，  
 
//     
void init()
{
    //      ，  ，  
    cin >> nodenum >> edgenum >> source;
    for(int i=1; i<=nodenum; ++i)
        dist[i] = maxint;
    dist[source] = 0;
    for(int i=1; i<=edgenum; ++i)
    {
        cin >> edge[i].u >> edge[i].v >> edge[i].weight;
        if(edge[i].u == source)          //          
            dist[edge[i].v] = edge[i].weight;
    }
}
 
//     
void relax(int u, int v, int weight)
{
    if(dist[v] > dist[u] + weight)
        dist[v] = dist[u] + weight;
}
 
bool Bellman_Ford()
{
    for(int i=1; i<=nodenum-1; ++i)
        for(int j=1; j<=edgenum; ++j)
            relax(edge[j].u, edge[j].v, edge[j].weight);
    bool flag = 1;
    //         
    for(int i=1; i<=edgenum; ++i)
        if(dist[edge[i].v] > dist[edge[i].u] + edge[i].weight)
        {
            flag = 0;
            break;
        }
    return flag;
}
int main()
{
    //freopen("input3.txt", "r", stdin);
    init();
    if(Bellman_Ford())
        for(int i = 1 ;i <= nodenum; i++)
            cout << dist[i] << endl;
    return 0;
}
  
SPFA 
초기 화 할 때 가장자리 만 추가 하고, 가장자리 에 추가 하지 않 으 면 버 티 지 않 습 니 다.
대기 열 을 사용 하여 Bellman - ford 알고리즘 을 최적화 하 는 원 리 는 다음 과 같다.
매번 모든 변 을 한 번 씩 이완 시 키 는 것 은 아니 며, 지난번 에 업 데 이 트 된 점 과 연 결 된 변 만 이 다음 이완 에 효과 가 있다.SPFA 는 이런 것들 을 기 록 했 습 니 다. 방금 업데이트 가 됐 습 니 다.
한 점 이 N 번 들 어가 면 이 그림 에 고리 가 있다 고 판단 하고 퇴장 합 니 다.팀 이 비 거나 탈퇴 합 니 다.
초기 화 할 때 시작 점 만 들 어 갑 니 다.
/*
	            (                )
	      (       ，       )    point  
	   point ，            1(   v+1   ),    point[1]=1,point[v+1]=E+1.
	    i,                   [point[i],point[i+1]-1]
	  point[i]=point[i+1]，       。
*/
int SPFA(int source)
{
	int i,j,flag,node;
	int tag[nodenum]={0};
	for(i=0;idist[u[i]]+w[i])
			{
				dist[v[i]]=dist[u[i]]+w[i],heap[tail++]=v[i];
				tag[v[i]]++;
				if(tag[v[i]]>=nodenum)
					return 1;

			}
		
	}