Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- using namespace std;
- int minDistance(int*, int*, int);
- void printPath(int*, int);
- int main() {
- cout << "Unesite broj cvorova koji se nalaze u mrezi" << endl;
- int n;
- cin >> n;
- cout << "Za svaki par cvorova navesti tezinu grane izmedju njih:" << endl;
- int** matrix = new int* [n];
- for (int i = 0; i < n; matrix[i++] = new int[n]);
- for (int i = 0; i < n; i++)
- for (int j = 0; j < n; j++) {
- cout << "(" << i << ", " << j << ") :";
- cin >> matrix[i][j];
- cout << endl;
- }
- cout << "Od kog cvora se racunaju najkraci putevi? ";
- int root;
- cin >> root;
- int* dist = new int[n];
- int* sptSet = new int[n];
- int* parent = new int[n];
- for (int i = 0; i < n; i++) {
- parent[i] = -1;
- dist[i] = INT_MAX;
- sptSet[i] = 0;
- }
- dist[root] = 0;
- for (int count = 0; count < n - 1; count++) {
- int u = minDistance(dist, sptSet, n);
- sptSet[u] = 1;
- for (int v = 0; v < n; v++)
- if (!sptSet[v] && matrix[u][v] &&
- dist[u] + matrix[u][v] < dist[v])
- {
- parent[v] = u;
- dist[v] = dist[u] + matrix[u][v];
- }
- }
- for (int i = 0; i < n; i++) {
- if (i != root) {
- cout << "Udaljenost cvora " << i << " od cvora " << root << " je " << dist[i] << endl;
- cout << "Putanja: " << root;
- printPath(parent, i);
- cout << endl;
- }
- }
- system("pause");
- for (int i = 0; i < n; i++) delete[] matrix[i];
- delete[] matrix;
- delete[] dist;
- delete[] sptSet;
- delete[] parent;
- return 0;
- }
- int minDistance(int* dist, int* sptSet, int n) {
- int min = INT_MAX, min_index;
- for (int v = 0; v < n; v++)
- if (sptSet[v] == false &&
- dist[v] <= min)
- min = dist[v], min_index = v;
- return min_index;
- }
- void printPath(int* parent, int j) {
- if (parent[j] == -1) return;
- printPath(parent, parent[j]);
- cout << "->" << j;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement