Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <limits.h>
- using namespace std;
- #define FOR(i, x, v) for(int i=x;i<v;i++)
- #define V 9
- void printPath(int points[], int i){
- if(points[i]==-1){
- return;
- }
- printPath(points, points[i]);
- cout << i << " ";
- }
- void printSolution(int dist[], int points[]) {
- printf("Titik Jarak dari titik awal\tPath\n");
- FOR(i, 0, V){
- printf("%d \t\t %d \t\t ", i, dist[i]);
- printPath(points, i);
- cout << endl;
- }
- }
- int findMin(int dist[], bool visited[]){
- int min = INT_MAX, minIndex;
- FOR(i, 0, V){
- if(visited[i]==false && dist[i]<=min){
- minIndex = i;
- min = dist[i];
- }
- }
- cout << "Min is " << minIndex << endl;
- return minIndex;
- }
- void shortestPath(int data[V][V], int fPoint){
- int dist[V];
- int points[V];
- bool visited[V] = {false};
- FOR(i, 0, V){
- dist[i] = INT_MAX;
- }
- dist[fPoint] = 0;
- points[fPoint] = -1;
- FOR(i, 0, V-1){
- int x = findMin(dist, visited);
- visited[x] = true;
- FOR(y, 0, V){
- if(!visited[y] && data[x][y] && dist[x]!=INT_MAX && dist[x]+data[x][y]<dist[y]){
- dist[y] = dist[x] + data[x][y];
- cout << "Dist y is " << dist[y] << endl;
- points[y] = x;
- }
- }
- }
- printSolution(dist, points);
- }
- int main(){
- int data[V][V] = {{0, 4, 0, 0, 0, 0, 0, 8, 0},
- {4, 0, 8, 0, 0, 0, 0, 11, 0},
- {0, 8, 0, 7, 0, 4, 0, 0, 2},
- {0, 0, 7, 0, 9, 14, 0, 0, 0},
- {0, 0, 0, 9, 0, 10, 0, 0, 0},
- {0, 0, 4, 14, 10, 0, 2, 0, 0},
- {0, 0, 0, 0, 0, 2, 0, 1, 6},
- {8, 11, 0, 0, 0, 0, 1, 0, 7},
- {0, 0, 2, 0, 0, 0, 6, 7, 0}};
- shortestPath(data, 0);
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement