📄 data_struct/图.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
#include <bits/stdc++.h>
using namespace std;
#define MAX_VERTEX 100
#define MAX 65535
typedef struct
{
int arcs[MAX_VERTEX][MAX_VERTEX];
int vNum;
} MGraph;
int FindMin(int Disk[], bool S[], int n)
{
int k = 0, min = MAX;
for (int i = 0; i < n; i++)
{
if (!S[i] && min > Disk[i])
{
min = Disk[i];
k = i;
}
}
if (min == MAX)
return -1;
return k;
}
void Print(int D[], int P[], int n)
{
for (int i = 0; i < n; i++)
{
cout << "V" << i << ": " << D[i] << "\tV" << i;
int pre = P[i];
while (pre != -1)
{
cout << "<-V" << pre;
pre = P[pre];
}
cout << endl;
}
}
void ShortPath(MGraph G, int v, int Disk[], int Path[])
{
bool S[MAX_VERTEX];
for (int i = 0; i < G.vNum; i++)
{
S[i] = false;
Disk[i] = G.arcs[v][i];
if (Disk[i] != MAX)
Path[i] = v;
else
Path[i] = -1;
}
S[v] = true;
Disk[v] = 0;
for (int i = 0; i < G.vNum; i++)
{
if ((v = FindMin(Disk, S, G.vNum)) == -1)
return;
S[v] = true;
for (int j = 0; j < G.vNum; j++)
{
if (!S[j] && (Disk[j] > G.arcs[v][j] + Disk[v]))
{
Disk[j] = G.arcs[v][j] + Disk[v];
Path[j] = v;
}
}
}
Print(Disk, Path, G.vNum);
}
void ShortPath_Optimized(MGraph G, int v, int Disk[], int Path[])
{
bool S[MAX_VERTEX];
for (int i = 0; i < G.vNum; i++)
{
S[i] = false;
Disk[i] = G.arcs[v][i];
if (Disk[i] != MAX)
Path[i] = v;
else
Path[i] = -1;
}
S[v] = true;
Disk[v] = 0;
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
for (int i = 0; i < G.vNum; i++)
{
pq.push({Disk[i], i});
}
while (!pq.empty())
{
auto p = pq.top();
pq.pop();
int u = p.second;
if (S[u])
continue;
S[u] = true;
for (int j = 0; j < G.vNum; j++)
{
if (!S[j] && (Disk[j] > G.arcs[u][j] + Disk[u]))
{
Disk[j] = G.arcs[u][j] + Disk[u];
Path[j] = u;
pq.push({Disk[j], j});
}
}
}
Print(Disk, Path, G.vNum);
}