Embedded Files
Algorithm TSP
Input: Integer c[max][max], Integer tour[max], Integer start, Integer n
Output: Minimum cost of TSP
Integer i, j, k
Integer temp[max], mintour[max]
Integer mincost, cost
If start = n - 2
Return c[tour[n-2]][tour[n-1]] + c[tour[n-1]][0]
End If
mincost = infinity
For i = start + 1 to n - 1
For j = 0 to n - 1
temp[j] = tour[j]
tour[start+1] = tour[i]
temp[i] = tour[start+1]
End For
cost = TSP(c, temp, start + 1, n)
If c[tour[start]][tour[i]] + cost < mincost
mincost = c[tour[start]][tour[i]] + cost
For k = 0 to n - 1
mintour[k] = temp[k]
End For
End If
End For
For i = 0 to n - 1
tour[i] = mintour[i]
Return mincost
End For
Return 0
End Algorithm
Algorithm Main
Input: Integer n, Integer c[max][max], Integer tour[max], Integer cost
Output "How many cities to travel"
Read n
Output "Enter the matrix"
For i = 0 to n - 1
For j = 0 to n - 1
Read c[i][j]
End For
End For
For i = 0 to n - 1
tour[i] = i
cost = TSP(c, tour, 0, n)
Output "Minimum cost = ", cost
For i = 0 to n - 1
Output tour[i] + 1, "1"
End For
End For
End Algorithm
Algorithm Knapsack
Input: Capacity rc, Number of objects n, Arrays w[], p[], r[], x[], tp
Output: Solution vector x[] and total profit tp
Initialize count = 0
Output "Enter the capacity"
Read rc
Output "Enter the number of objects"
Read n
For i = 1 to n
Output "Enter the weight of object", i
Read weight
Output "Enter the profit of object", i
Read profit
value = (float)profit / weight
location = Check(value)
r[location] = value
w[location] = weight
p[location] = profit
count = count + 1
End For
For i = 1 to n
If rc > w[i]
x[i] = 1
tp = tp + p[i]
rc = rc - w[i]
Else If rc < w[i]
x[i] = (float)rc / w[i]
tp = tp + p[i] * x[i]
rc = rc - w[i] * x[i]
End If
End For
For i = 1 to n
Output "x[", i, "] =", x[i]
End For
Output "Total profit =", tp
End Algorithm
Function Check(value)
Input: Value to check
Output: Location in the array r[]
Set i = 1
While r[i] > value
i = i + 1
End While
For j = count to i step -1
r[j + 1] = r[j]
w[j + 1] = w[j]
p[j + 1] = p[j]
End For
Return i
End Function
Algorithm for KruskalsAlgorithm
Input: n (number of nodes), m (number of edges)
Output: Minimum Spanning Tree (MST)
Array c[40][40] // Cost matrix
Array parent[100] // Array to track parent nodes
Integer i, j, u, v, a, b, n, m, w, min, de = 0, tc = 0
Integer parent[100] initialized to 0
Output "Enter the number of nodes"
Read n
Output "Enter the number of edges"
Read m
For i = 0 to n
parent[i] = i
For j = 0 to n
c[i][j] = 9999
End For
End For
Call print()
For i = 1 to m
Output "Enter the connection"
Read u, v
Output "Enter the cost"
Read w
c[u][v] = c[v][u] = w
End For
Call print()
While de < n - 1
min = 9999
For i = 0 to n
For j = 0 to n
If c[i][j] < min
min = c[i][j]
a = u = i
b = v = j
End If
End For
End For
While parent[u] != u
u = parent[u]
End While
While parent[v] != v
v = parent[v]
End While
If u != v
Output "a TO b = min"
parent[v] = u
tc = tc + min
de = de + 1
End If
c[a][b] = c[b][a] = 9999
End While
Output "MINIMUM COST = tc"
End Algorithm
Algorithm for Prim's MST
Input: n (number of vertices), e (number of edges), mat[20][20] (adjacency matrix)
Output: Prints the Minimum Spanning Tree and its total cost
Integer Array visit[20], Initialize de = 0, tc = 0, src, u, v, min, weight
Initialize mat[20][20] with all elements set to 9999
Output "Enter the no.of vertice"
Read n
Output "Enter the number of edges"
Read e
For i = 1 to n
For j = 1 to n
mat[i][j] = 9999
End For
End For
Call print
For i = 1 to e
Output "Enter the connections ", i
Read u, v
Output "Enter the weight ", i
Read weight
mat[u][v] = mat[v][u] = weight
End For
Call print
Output "Enter the source"
Read src
visit[src] = 1
While de < n - 1
min = 9999
For i = 1 to n
If visit[i] != 0
For j = 1 to n
If mat[i][j] < min
min = mat[i][j]
u = i
v = j
End If
End For
End If
End For
If visit[v] != 1
Output u, " TO ", v, " = ", min
de = de + 1
visit[v] = 1
tc = tc + min
End If
mat[u][v] = mat[v][u] = 9999
End While
Output "Total Cost is ", tc
End Algorithm
TREE MST FOR THAT TREE
Page updated
Google Sites
Report abuse