Коды основных функций / [Код основных функций] Лаб. 5
.pdf
[Код основных функций] Лабораторная работа №5. Кратчайший путь в графе
//Get the current time.
//This function should be used only for measuring time
//(first call, algorithm, second call; then the difference between the values) double getProcTime() {
#if defined(_WIN32) // If Windows:
FILETIME createTime, exitTime, kernelTime, userTime;
if (GetProcessTimes(GetCurrentProcess(), &createTime, &exitTime, &kernelTime, &userTime) != -1)
return (ULARGE_INTEGER { {userTime.dwLowDateTime, userTime.dwHighDateTime } }).QuadPart / 10000000.L;
return 0;
#else // If Linux or MacOS:
return double(clock()) / CLOCKS_PER_SEC; #endif
}
/* Input:
vector<vector<float>> matrix { {0, 1.5, 0, 0, 0, 0, 0}, {1, 0.0, 1.5, 9, 9, 9, 9}, {0, 1.0, 0, 1.5, 9, 9, 9}, {0, 9, 1.0, 0, 1.5, 9, 9}, {0, 9, 9, 1.0, 0, 1.5, 9}, {0, 9, 9, 9, 1.0, 0, 1.5}, {0, 9, 9, 9, 9, 1.0, 0.0}
};
Output:
Dijkstra's algorithm:
Vector of distances: 0.000000 1.500000 3.000000 4.500000 6.000000 7.500000 9.000000
Vector of parents: 0 0 1 2 3 4 5 Bellman-Ford algorithm:
Vector of distances: 0.000000 1.500000 3.000000 4.500000 6.000000 7.500000 9.000000
Vector of parents: 0 0 1 2 3 4 5 Levit's algorithm:
Vector of distances: 0.000000 1.500000 3.000000 4.500000 6.000000 7.500000 9.000000
Vector of parents: 0 0 1 2 3 4 5
*/
// Dijkstra's algorithm template <class T = int>
std::pair<std::vector<T>, std::vector<int>> dijkstraAlgorithm(const std::vector<std::vector<T>> & matrix, int start) {
const T INF = std::numeric_limits<T>::max(); const int n = matrix.size();
std::vector<T> distance(n, INF); std::vector<int> parent(n, -1); distance[parent[start] = start] = 0; std::priority_queue<std::pair<T, int>> q; q.push({ 0, start });
while (!q.empty()) {
T dist = -q.top().first; int v = q.top().second; q.pop();
if (dist > distance[v]) continue;
for (int to = 0, len = matrix[v].size(); to < len; ++to) { dist = matrix[v][to];
if (dist > 0 && distance[v] + dist < distance[to]) { distance[to] = distance[parent[to] = v] + dist; q.push({ -distance[to], to });
}
}
}
return { distance, parent };
}
// Bellman-Ford algorithm template <class T = int>
std::pair<std::vector<T>, std::vector<int>> bellmanFordAlgorithm(const std::vector<std::vector<T>> & matrix, int start) {
const T INF = std::numeric_limits<T>::max(); const int n = matrix.size();
std::vector<T> distance(n, INF); std::vector<int> parent(n, -1); distance[parent[start] = start] = 0; bool any;
do {
any = false;
for (int i = 0; i < n; ++i) { for (int j = 0; j < n; ++j) {
T dist = matrix[i][j];
if (dist > 0 && dist + distance[i] < distance[j]) { distance[j] = dist + distance[parent[j] = i]; any = true;
}
}
}
} while (any);
return { distance, parent };
}
// Levit's algorithm template <class T = int>
std::pair<std::vector<T>, std::vector<int>> levitAlgorithm(const
std::vector<std::vector<T>> & matrix, int start) { const T INF = std::numeric_limits<T>::max(); const int n = matrix.size();
std::vector<T> distance(n, INF); std::vector<int> parent(n, -1); std::vector<char> state(n, 2); distance[parent[start] = start] = 0; state[start] = 1;
std::deque<int> q(1, start); while (!q.empty()) {
int from = q.front(); q.pop_front(); state[from] = 0;
for (int to = 0, len = matrix[from].size(); to < len; ++to) { T dist = matrix[from][to];
if (dist > 0 && distance[to] > distance[from] + dist) { distance[to] = distance[parent[to] = from] + dist; if (state[to] == 2) q.emplace_front(to);
else if (state[to] == 0) q.emplace_back(to); state[to] = 1;
}
}
}
return { distance, parent };
}
Тестирование производится на симметричных матрицах смежности со случайными весами и нулями по диагонали (то есть не всякий граф такой матрицы можно отобразить на координатной плоскости с учетом всех весов).