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
|
#include <cmath>
#include <queue>
const int numcities = 744;
struct compare
{
bool operator()(const int& l, const int& r)
{
return l > r;
}
};
int distance(int nd1, int nm1, int wd1, int wm1, int nd2, int nm2, int wd2, int wm2)
{
float lat1 = nd1 + ((float)nm1 / 60);
float long1 = wd1 + ((float)wm1 / 60);
float lat2 = nd2 + ((float)nm2 / 60);
float long2 = wd2 + ((float)wm2 / 60);
return ((int)(sqrt(((lat2 - lat1)*(lat2 - lat1)) + ((long2 - long1) * (long2 - long1)))));
}
void adjmats(int nd[], int nm[], int wd[], int wm[], int am[][numcities])
{
for (int i = 0; i < numcities; i++)
{
for (int j = 0; j < numcities; j++)
{
int distances = distance(nd[i],nm[i],wd[i],wm[i],nd[j],nm[j],wd[j],wm[j]);
am[i][j] = distances;
//cout << "ran " << i << j;
}
}
}
void prims(int nd[], int nm[], int wd[], int wm[], string name[])
{
int adjmat[numcities][numcities];
for (int i = 0; i < numcities; i++)
{
for (int j = 0; j < numcities; j++)
{
adjmat[i][j] = 0;
}
}
cout << adjmat[743][664]; //Seg faults when trying to access this value.
//Put any that are within 1500 miles of the start, s (Washington D.C.) into an adjacency matrix.
//Need to make a matrix and list creation.
//Repeat for all cities.
adjmats(nd, nm, wd, wm, adjmat);
//Make two new arrays, one which will point to parent arrays and
//one which will be the edge weights (key)
string parent[numcities];
int key[numcities];
//Set washington D.C's parent to Null and Key to 0.
key[0] = 0;
for(int q = 1; q < numcities; q++)
{
key[q] = 9999;
parent[q] = " ";
}
//Put the A.M. into a queue, start at 0 (Washington D.C)
//Make a for loop, in that for loop make another for loop. Put all those values
//into the queue, then out of the inner for loop check.
//For each city, check all the ones in that arrays list -> current city is u.
// If v is in the queue and the distance between u and v < key of v,
// v's parent is u, v's key is key of u + distance between u and v.
// to figure out which v is correct, first put all the distance(v) values into an array(large size)
// then simply run through after sorting (Set minimum value into a integer) all the values in the array.
// for int i = u+1; i < max; i++)
// a[v] = distance u,v
// blah.push(distance u,v);
priority_queue<int,vector<int>, compare > pq;
for (int a = 0; a < numcities; a++)
{
for (int b = a + 1; b < numcities; b++)
{
pq.push(adjmat[a][b]);
}
while ( !pq.empty() )
{
int temp = pq.top();
int e = 0, f = 0;
for (int c = 0; c < numcities; c++)
{
for (int d = c + 1; d < numcities; d++)
{
bool found = false;
if (!found)
{
if(adjmat[c][d] == temp)
{
found = true;
e = c;
f = d;
}
}
}
}
if (adjmat[e][f] < key[b])
{
parent[b] = name[a];
key[b] = key[a] + adjmat[a][b];
}
pq.pop();
}
cin.get();
}
for (int t = 1; t < numcities; t++)
{
cout << name[t] << " --" << key[t] << "-> " << parent[t] << endl;
}
//Output each city and it's parent. (Probably excluding D.C.)
}
|
