-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.cpp
146 lines (134 loc) · 3.98 KB
/
main.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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include <iostream>
using namespace std;
#include <stdio.h>
#include <limits.h>
#define V 9
// A utility function to find the vertex with minimum distance
// value, from the set of vertices not yet included in shortest
// path tree
int minDistance(int dist[], bool sptSet[])
{
int min = INT_MAX, min_index;
for (int v = 0; v < V; v++)
if (sptSet[v] == false && dist[v] <= min)
min = dist[v], min_index = v;
return min_index;
}
// Function to print shortest path from source to j
// using parent array
void printPath(int parent[], int j)
{
if (parent[j]==-1)
return;
printPath(parent, parent[j]);
printf("%d ", j);
}
// A utility function to print the constructed distance
// array
int printSolution(int dist[], int n, int parent[])
{
int src = 0;
printf("Vertex\t Distance\tPath");
for (int i = 1; i < V; i++)
{
printf("\n%d -> %d \t\t %d\t\t%d ", src, i, dist[i], src);
printPath(parent, i);
}
}
void allotment(char busn[][5], int dist[], int parent[],int n)
{int order[V];
for(int i=0;i<V;i++)
order[i]=dist[i];
int temp;
for(int k = 0; k< V-1; k++) {
for(int i = 0; i < V-k-1; i++) {
if(order[ i ] < order[ i+1] ) {
temp = order[ i ];
order[ i ] = order[ i+1 ];
order[ i + 1] = temp;
}
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<V;j++)
{
if(order[i%(V-1)]==dist[j])
{
cout<<"\n";
for(int m=0;m<5;m++)
cout<<busn[i][m];
cout<<"\t is scheduled along :\t\t"<<0<<" ";
printPath(parent,j);
}
}
}
return;
}
// Function that implements Dijkstra's single source shortest path
// algorithm for a graph represented using adjacency matrix
// representation
void dijkstra(int graph[V][V], int src)
{
int dist[V]; // The output array. dist[i] will hold
// the shortest distance from src to i
bool sptSet[V];
int parent[V];
for (int i = 0; i < V; i++)
{
parent[0] = -1;
dist[i] = INT_MAX;
sptSet[i] = false;
}
dist[src] = 0;
// Find shortest path for all vertices
for (int count = 0; count < V-1; count++)
{
int u = minDistance(dist, sptSet);
sptSet[u] = true;
for (int v = 0; v < V; v++)
{
if (!sptSet[v] && graph[u][v] &&
dist[u] + graph[u][v] < dist[v])
{
parent[v] = u;
dist[v] = dist[u] + graph[u][v];
}
}
}
// print the constructed distance array
printSolution(dist, V, parent);
int n;
cout<<"\n Enter number of buses available at the depot:";
cin>>n;
char busn[n][5];
for(int i=0;i<n;i++)
{
cout<<"\n Enter bus no: ";
cin>>busn[i];
}
allotment(busn,dist,parent,n);
}
// driver program to test above function
int main()
{
cout<<" ******************************************************************************"<<endl;
cout<<" ******* ******* ******* ******* ******* ******* ******* ******* *******"<<endl;
cout<<" * City Bus Scheduling System*"<<endl;
cout<<" * Mumbai Transport Service *"<<endl;
cout<<" ******* ******* ******* ******* ******* ******* ******* ******* *******"<<endl;
cout<<" ******************************************************************************"<<endl;
/* Let us create the example graph discussed above */
int graph[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, 0, 10, 0, 2, 0, 0},
{0, 0, 0, 14, 0, 2, 0, 1, 6},
{8, 11, 0, 0, 0, 0, 1, 0, 7},
{0, 0, 2, 0, 0, 0, 6, 7, 0}
};
dijkstra(graph, 0);
return 0;
}