-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathProgramacioDinamica_INICI_DESTI.cpp
117 lines (108 loc) · 3.73 KB
/
ProgramacioDinamica_INICI_DESTI.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
#include "pch.h"
#include "Graph.h"
#include "GraphApplicationDlg.h"
#include <queue>
// =============================================================================
// ProgramacioDinamica_INICI_DESTI =============================================
// =============================================================================
CTrack DijkstraQueueINICI_DESTI(CGraph& graph)
{
struct CPair {
CVertex* m_pVertex;
double m_Distance;
CPair(CVertex* pV, double d) : m_pVertex(pV), m_Distance(d) {}
};
struct comparator {
bool operator()(CPair& pair1, CPair& pair2) {
return pair1.m_Distance > pair2.m_Distance;
}
};
CVertex* pInici = graph.GetVertex("INICI");
CVertex* pDesti = graph.GetVertex("DESTI");
priority_queue<CPair, std::vector<CPair>, comparator> queue;
for (CVertex& v : graph.m_Vertices) {
v.m_DijkstraVisit = false;
v.m_DijkstraDistance = numeric_limits<double>::max();
}
pInici->m_DijkstraDistance = 0;
pInici->m_pDijkstraPrevious = NULL;
queue.push(CPair(pInici, 0.0));
while (!queue.empty()) {
CVertex* pVMin = queue.top().m_pVertex;
double pairDistance = queue.top().m_Distance;
queue.pop();
if (pairDistance == pVMin->m_DijkstraDistance) {
pVMin->m_DijkstraVisit = true;
for (CEdge* pE : pVMin->m_Edges) {
double d = pVMin->m_DijkstraDistance + pE->m_Length;
if (pE->m_pDestination->m_DijkstraDistance > d) {
pE->m_pDestination->m_DijkstraDistance = d;
pE->m_pDestination->m_pDijkstraPrevious = pE;
queue.push(CPair(pE->m_pDestination, d));
}
}
}
}
CTrack cami(&graph);
while (pDesti != pInici) {
cami.m_Edges.push_front(pDesti->m_pDijkstraPrevious);
pDesti = pDesti->m_pDijkstraPrevious->m_pOrigin;
}
return cami;
}
// =============================================================================
// TrobaCamiProgramacioDinamicaBB ==============================================
// =============================================================================
CTrack TrobaCamiProgramacioDinamicaBB(CGraph& graph)
{
struct CNode {
CVertex* m_pVertex;
double m_Distance;
double m_Estimacio;
CNode(CVertex* pV, double d, double estimacio) : m_pVertex(pV), m_Distance(d), m_Estimacio(estimacio) {}
};
struct comparator {
bool operator()(CNode& node1, CNode& node2) {
return node1.m_Estimacio > node2.m_Estimacio;
}
};
CVertex* pInici = graph.GetVertex("INICI");
CVertex* pDesti = graph.GetVertex("DESTI");
SolutionNodesCreated = 0;
SolutionNodesBranched = 0;
priority_queue<CNode, std::vector<CNode>, comparator> queue;
for (CVertex& v : graph.m_Vertices) {
v.m_DijkstraVisit = false;
v.m_DijkstraDistance = numeric_limits<double>::max();
}
pInici->m_DijkstraDistance = 0;
pInici->m_pDijkstraPrevious = NULL;
queue.push(CNode(pInici, 0.0, 0.0));
++SolutionNodesCreated;
while (!queue.empty()) {
CVertex* pVMin = queue.top().m_pVertex;
double pairDistance = queue.top().m_Distance;
queue.pop();
if (pairDistance == pVMin->m_DijkstraDistance) {
pVMin->m_Color = RGB(255, 100, 0);
if (pVMin == pDesti) break;
for (CEdge* pE : pVMin->m_Edges) {
pE->SetColor(RGB(255, 100, 0));
double d = pVMin->m_DijkstraDistance + pE->m_Length;
if (pE->m_pDestination->m_DijkstraDistance > d) {
pE->m_pDestination->m_DijkstraDistance = d;
pE->m_pDestination->m_pDijkstraPrevious = pE;
queue.push(CNode(pE->m_pDestination, d, d+pDesti->m_Point.Distance(pE->m_pDestination->m_Point)));
++SolutionNodesCreated;
}
}
++SolutionNodesBranched;
}
}
CTrack cami(&graph);
while (pDesti!=pInici) {
cami.m_Edges.push_front(pDesti->m_pDijkstraPrevious);
pDesti = pDesti->m_pDijkstraPrevious->m_pOrigin;
}
return cami;
}