Dijkstra 알고리즘 과 실현 - 진급 편
12078 단어 dijkstra작은 뿌리 더미 실현
우선, 앞의 IsInS 구 조 를 vector < int > S, vector < int > Q 로 나 누 어 최소 로 쉽게 실현 할 수 있 고 S 도 삭제 할 수 있 습 니 다. 수 정 된 코드 는 다음 과 같 습 니 다.
#include <iostream>
#include <iostream>
#include <vector>
#include <stack>
#include<algorithm>
#include "bheap.hpp"
using namespace std;
int map[][6] = { // ，
{0, 6, 3, INT_MAX, INT_MAX, INT_MAX},
{6, 0, 2, 5,INT_MAX, INT_MAX},
{3, 2, 0, 3,4, INT_MAX},
{INT_MAX,5, 3, 0, 2, 3},
{INT_MAX,INT_MAX, 4, 2, 0, 5},
{INT_MAX,INT_MAX,INT_MAX,3,5,0}
};
void init(int num, int startVertex,int distance[], int prevVertex[], vector<int>& Q)
{
/* distance prevVertex */
for(int i =0; i < num; ++i)
{
distance[ i ] = map[ startVertex ][ i ]; // ， INT_MAX
if(map[ startVertex ][ i ] < INT_MAX) //
prevVertex[ i ] = startVertex;
else
prevVertex[ i ] = -1; //
}
prevVertex[ startVertex ] = -1; //
for(int i =0; i < num; ++i)
{
if(i != startVertex)
{
Q.push_back(i);
}
}
}
void extractMin(vector<int>& Q,int distance[],int& currentVertex)
{
/* Q u j distance ， A C， D*/
int minDistance = INT_MAX;
vector<int>::iterator ite = Q.begin();
for(; ite!=Q.end();ite++) //
{
if((distance[*ite] < minDistance))// currentVertexA Q distance currentVertexC
{
currentVertex = *ite;
minDistance = distance[*ite];
}
}
return;
}
/* currentVertexC ， distance*/
void Relax(vector<int> Q,int distance[],int pre[],int& currentVertex)
{
vector<int>::iterator ite = Q.begin();
for(; ite!=Q.end();ite++)
{
if (map[currentVertex][*ite] < INT_MAX) // Q ， c->d,c->e, c->b
{
int currentdist = distance[ currentVertex] + map[ currentVertex ][*ite];
if (currentdist < distance[ *ite ]) //distance[j] j
{
distance[ *ite ] = currentdist;
pre[ *ite] = currentVertex;
}
}
}
}
void Dijkstra( const int numOfVertex, /* */
const int startVertex, /* */
int (map)[][6], /* */
int *distance, /* */
int *prevVertex /* */
)
{
vector<int> Q;
//step1
init(numOfVertex, startVertex,distance, prevVertex, Q);
/* S */
int currentVertex = startVertex;
for (int i = 1; i < numOfVertex; i ++) // 1 S ， numOfVertex-1
{
//step2
extractMin(Q,distance,currentVertex);
//S.push_back(currentVertex);
Q.erase(remove(Q.begin(),Q.end(),currentVertex),Q.end());
//step3
Relax(Q,distance,prevVertex,currentVertex);
}
}
int main (int argc, const char * argv[])
{
int distance[6];
int preVertex[6];
//for (int i =0 ; i < 5; ++i ) // i
//{
Dijkstra(6, 0, map, distance, preVertex);
//for(int j =0; j < 6; ++j)
//{
int index = 5; // for j
stack<int > trace;
while (preVertex[index] != -1) {
trace.push(preVertex[index]);
cout<<"push"<<preVertex[index]<<endl;
index = preVertex[index];
}
cout << " ：";
while (!trace.empty()) {
cout<<trace.top()<<" -- ";
trace.pop();
}
cout <<5; //j
cout <<" ："<<distance[5]<<endl; //j
// }
//}
system("pause");
return 0;
}
2. 이전의 기본 Dijkstra 알고리즘 의 실현 에서 extractMin () 알고리즘 은 O (n) 번 의 조작 이 있어 야 최소 값 을 찾 을 수 있 습 니 다.따라서 최소 더미 로 수정 하여 알고리즘 효율 이 O (logn) 작은 루트 더미 로 변 하 는 실현 은 앞에서 참고 할 수 있 습 니 다.
Dijkstra 알고리즘 + Heap 더미 완전 알고리즘 사상 앞의 글 에서 우 리 는 Dijkstra 알고리즘 이 다음 과 같다 는 것 을 알 게 되 었 다.
DIJKSTRA(G, w, s) 1 INITIALIZE-SINGLE-SOURCE(G, s) //1. 노드 작업 초기 화 2 S ← Ø 3 Q ← V[G] //2. 대기 열 초기 화 4 while Q ≠ Ø 5 do u ← EXTRACT - MIN (Q) / / 3, 최소 줄 에서 최소 노드 추출 (그 전에 최소 더미 만 들 기) 6 S ← S ∪{u} 7 for each vertex v ∈ Adj[u] 8 do RELAX(u, v, w) //4. 느슨 한 조작.
구현 코드 는 다음 과 같 습 니 다:
3.1 헤더 파일 bhap. hpp
#include <vector>
using namespace std;
inline bool mincmp(const int &x, const int &y)
{ return x < y; }
class DIST
{
public:
int index;
int dist;
DIST()
{
index =0;
dist = INT_MAX;
}
DIST& operator=( const DIST& d)
{
index = d.index;
dist=d.dist;
return *this;
}
};
class minHeap
{
public:
int n;//n Q
vector<DIST> Q;
public:
inline minHeap()
{
n=0;
Q = vector<DIST>(6);
}
inline void push(DIST x)// , ，
{
int hole = n++;//(0-n)
for(; hole > 0 && mincmp(x.dist, Q[hole >> 1].dist); hole = hole >> 1)//
{
Q[hole] = Q[(hole) >> 1];
}
Q[hole] = x;
}
inline void deletenode(int pos)// ， ，
{
int tmp;//(0-n-1)
DIST value = Q[pos];
int hole = pos;
int lc = (hole<<1)+1;
while(lc+1 < n)
{
tmp = (mincmp(Q[lc+1].dist, Q[lc].dist) )? (lc+1) : lc;
if(mincmp(Q[tmp].dist, Q[n-1].dist))
{
Q[hole] = Q[tmp];
lc = (lc<<1)+1;
//rc = lc+1;
hole =tmp;
}
else
{
break;
}
}
Q[hole] = Q[n-1];
//save n-1, ， value
Q[n-1] =value;
n--;
}
inline void pop()//
{
deletenode(0);
}
inline DIST top()
{
return Q[0];
}//
}; 알고리즘 구현 파일
<p> </p><p>#include <iostream>
#include <iostream>
#include <vector>
#include <stack>
#include<algorithm>
#include "bheap.hpp"
using namespace std;
int preVertex[6];
int map[][6] = { // ，
{0, 6, 3, INT_MAX, INT_MAX, INT_MAX},
{6, 0, 2, 5,INT_MAX, INT_MAX},
{3, 2, 0, 3,4, INT_MAX},
{INT_MAX,5, 3, 0, 2, 3},
{INT_MAX,INT_MAX, 4, 2, 0, 5},
{INT_MAX,INT_MAX,INT_MAX,3,5,0}
};
minHeap minh;
void initMinHeap(int num, int startVertex)
{
for(int i =0; i < num; ++i)
{
DIST tempdist;
tempdist.index = i;
tempdist.dist = map[ startVertex ][ i ];
minh.push(tempdist);
}
vector<DIST>::iterator ite = minh.Q.begin();
// Q BCDEF
minh.pop();// startVertex
}
void initPreVertex(int num, int startVertex)
{
for(int i =0; i<num;i++)
{
if(map[ startVertex ][ i ] < INT_MAX) //
preVertex[ i ] = startVertex;
else
preVertex[ i ] = -1; // </p><p> }
preVertex[ startVertex ] = -1; //
}
void init(int num, int startVertex)
{
/* distance prevVertex */
initMinHeap(num,startVertex);
initPreVertex(num,startVertex);
}
/* currentVertexC ， distance*/
void Relax(DIST& d)
{
vector<DIST>::iterator ite = minh.Q.begin();//store Q
int i =0;
int predist = d.dist;
int currentVertex = d.index;
for(; ite!= minh.Q.end() && i<minh.n ;i++, ite++) //deal with data in Q, the first n nums
{
if (map[currentVertex][ite->index] < INT_MAX) // Q ， c->d,c->e, c->b
{
int currentdist = predist + map[ currentVertex ][ite->index];
if (currentdist < ite->dist) //distance[j] j
{
ite->dist = currentdist;
preVertex[ite->index] = currentVertex;
}
}
}
}
void Dijkstra( const int numOfVertex, /* */
const int startVertex, /* */
int (map)[][6] /* */
)
{
//step1
init(numOfVertex, startVertex);//Q BCDEF
/* S */
int currentVertex = startVertex; //A
for (int i = 1; i < numOfVertex; i ++) // 1 S ， numOfVertex-1
{
//step2
DIST currentDist = minh.top();//extract min
minh.pop();
Relax(currentDist);
}
}
int main (int argc, const char * argv[])
{
for (int i =0 ; i < 5; ++i ) // i
{
Dijkstra(6, i, map);
for(int j =0; j < 6; ++j)
{
int index = j; // for j
stack<int > trace;
while (preVertex[index] != -1) {
trace.push(preVertex[index]);
cout<<"push"<<preVertex[index]<<endl;
index = preVertex[index];
}
cout << " ：";
while (!trace.empty()) {
cout<<trace.top()<<" -- ";
trace.pop();
}
cout <<j; //j
vector<DIST>::iterator ite = minh.Q.begin();
for(;ite!= minh.Q.end(); ite++)
{
if(ite->index == j)
{
cout <<" ："<<ite->dist<<endl; //j
}
}
}
}
system("pause");
return 0;
}
</p><p>
</p>이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[백준]#11779 최소비용 구하기 2n(1≤n≤1,000)개의 도시가 있다. 그리고 한 도시에서 출발하여 다른 도시에 도착하는 m(1≤m≤100,000)개의 버스가 있다. 우리는 A번째 도시에서 B번째 도시까지 가는데 드는 버스 비용을 최소화 시키려고...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
