//Final Result
sumAllPair = 0;
//Total Number of vertices
N
//Adjacency List
adjacencyList: array of linked list
//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N
//Initialize Matrix
loop ii from 0 to N-1 {
loop jj from 0 to N-1 {
if(ii equals jj) {
weightedGraph[ii][jj] = 0
}else {
weightedGraph[ii][jj] = INFINITY
}
}
}
currentVertex = 0
visitedSet: LinkedHashSet of Size N
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)
print sumAllPair
/*
* Say graph has vertices 1,2,3,4,5,6,7
*
* allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
* 21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
* where ij represents cost of path from vertex i to vertex j
*
* Time Complexity:
* N(N-1)/2 or Combination(N,2)
*/
function allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {
for each visitedVer in visitedSet{
cost = weightedGraph[visitedVer][lastVisitedVertex] + weightedGraph[lastVisitedVertex][currentVertex]
sumAllPair = sumAllPair + cost
weightedGraph[visitedVer][currentVertex] = cost
weightedGraph[currentVertex][visitedVer] = cost
}
add currentVertex to visitedSet
for each neighbourVert in adjacencyList[currentVertex] {
if(neighbourVert not equals lastVisitedVertex) {
//neighbourVert becomes currentVertex
//currentVertex becomes lastVisitedVertex
call allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
}
}
}
Algorithm to compute sum of cost of all path between pair of unique edge pairsvertices of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all edge pairspath between pair of unique vertices.
Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the java implementationpseudocode.
import java.util.*;
public class AllPairSumTree {
//Final Result
static long sumAllPairssumAllPair = 0;
public static void main(String[] args) {
/*
* /Total Number of vertices
*/
int N = 7;
/*
* Adjacency List
*/
LinkedList<Integer>[] adjacencyList = new LinkedList[N];
/*
* Initialize Adjacency List
*/
for(int ii=0; ii<N;ii++) {
adjacencyList: adjacencyList[ii]array =of newlinked LinkedList<Integer>();list
}
/*
* /Weighted Graph Matrix
*/
int[][] weightedGraph = new int[N][N];
: two dimensional integer array /*N*N
*
//Initialize Matrix
*/
loop ii from 0 for(intto ii=0;ii<N;ii++)N-1 {
loop jj from 0 for(intto jj=0;jj<N;jj++)N-1 {
if(ii ==equals jj) {
weightedGraph[ii][jj] = 0;0
}else {
weightedGraph[ii][jj] = Integer.MAX_VALUE;INFINITY
}
}
}
/*
* Input Pattern: vertex1, vertex2, cost
*
* Total Vertex: N, Total Edges: N-1 (Tree, Undirected Graph)
*/
int[] inputGraph = { 1, 2, 1,
2, 3, 2,
3, 4, 3,
3, 5, 4,
5, 6, 6,
5, 7, 5};
/*
* Assign Adjacency List and Matrix with input Graph
*/
for(int ii=0; ii<N-1; ii++) {
int vertex1 = inputGraph[ii*3 + 0] - 1;
int vertex2 = inputGraph[ii*3 + 1] - 1;
int cost = inputGraph[ii*3 + 2];
adjacencyList[vertex1].add(vertex2);
adjacencyList[vertex2].add(vertex1); //bidirectional edge
weightedGraph[vertex1][vertex2] = cost;
weightedGraph[vertex2][vertex1] = cost; //bidirectional edge
}
sumAllPairs = 0;
int currentVertex = 0;0
LinkedHashSet<Integer> visitedSet: =LinkedHashSet newof LinkedHashSet<Integer>(Size N);
int lastVisitedVertex = -1;1
call allPairSumallVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex);
print System.out.println(sumAllPairs);sumAllPair
}
/*
* Say graph has vertices 1,2,3,4,5,6,7
*
* allPairSumallVertexPairSum() will compute sum of edgescost likeof this:
all path between pair of unique vertices like this:
* 21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
* where ij represents edgecost of path from vertex i to vertex j
*
* Time Complexity:
* N(N-1)/2 or Combination(N,2)[![enter image description here][1]][1]
*/
private static void allPairSumallVertexPairSum(int[][] weightedGraph, LinkedList<Integer>[] adjacencyList, int currentVertex, LinkedHashSet<Integer> visitedSet, int lastVisitedVertex) {
for each for(Integer visitedVer :in visitedSet) {
int cost = weightedGraph[visitedVer][lastVisitedVertex] + weightedGraph[lastVisitedVertex][currentVertex];weightedGraph[lastVisitedVertex][currentVertex]
sumAllPair = sumAllPairssumAllPair +=+ cost;cost
weightedGraph[visitedVer][currentVertex] = cost;cost
weightedGraph[currentVertex][visitedVer] = cost;cost
}
add currentVertex to visitedSet.add(currentVertex);
for(Integer each neighbourVert :in adjacencyList[currentVertex]) {
if(neighbourVert !=not equals lastVisitedVertex) {
/*
* /neighbourVert becomes currentVertex
* //currentVertex becomes lastVisitedVertex
*/
allPairSumallVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex);
}
}
}
}
Here is an example:
Algorithm to compute sum of all unique edge pairs of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of all edge pairs. Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the java implementation.
import java.util.*;
public class AllPairSumTree {
static long sumAllPairs = 0;
public static void main(String[] args) {
/*
* Total Number of vertices
*/
int N = 7;
/*
* Adjacency List
*/
LinkedList<Integer>[] adjacencyList = new LinkedList[N];
/*
* Initialize Adjacency List
*/
for(int ii=0; ii<N;ii++) {
adjacencyList[ii] = new LinkedList<Integer>();
}
/*
* Weighted Graph Matrix
*/
int[][] weightedGraph = new int[N][N];
/*
* Initialize Matrix
*/
for(int ii=0;ii<N;ii++) {
for(int jj=0;jj<N;jj++) {
if(ii == jj) {
weightedGraph[ii][jj] = 0;
}else {
weightedGraph[ii][jj] = Integer.MAX_VALUE;
}
}
}
/*
* Input Pattern: vertex1, vertex2, cost
*
* Total Vertex: N, Total Edges: N-1 (Tree, Undirected Graph)
*/
int[] inputGraph = { 1, 2, 1,
2, 3, 2,
3, 4, 3,
3, 5, 4,
5, 6, 6,
5, 7, 5};
/*
* Assign Adjacency List and Matrix with input Graph
*/
for(int ii=0; ii<N-1; ii++) {
int vertex1 = inputGraph[ii*3 + 0] - 1;
int vertex2 = inputGraph[ii*3 + 1] - 1;
int cost = inputGraph[ii*3 + 2];
adjacencyList[vertex1].add(vertex2);
adjacencyList[vertex2].add(vertex1); //bidirectional edge
weightedGraph[vertex1][vertex2] = cost;
weightedGraph[vertex2][vertex1] = cost; //bidirectional edge
}
sumAllPairs = 0;
int currentVertex = 0;
LinkedHashSet<Integer> visitedSet = new LinkedHashSet<Integer>(N);
int lastVisitedVertex = -1;
allPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex);
System.out.println(sumAllPairs);
}
/*
* Say graph has vertices 1,2,3,4,5,6,7
*
* allPairSum() will compute sum of edges like this:
* 21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
* where ij represents edge from vertex i to vertex j
*
* Time Complexity:
* N(N-1)/2 or Combination(N,2)[![enter image description here][1]][1]
*/
private static void allPairSum(int[][] weightedGraph, LinkedList<Integer>[] adjacencyList, int currentVertex, LinkedHashSet<Integer> visitedSet, int lastVisitedVertex) {
for(Integer visitedVer : visitedSet) {
int cost = weightedGraph[visitedVer][lastVisitedVertex] + weightedGraph[lastVisitedVertex][currentVertex];
sumAllPairs += cost;
weightedGraph[visitedVer][currentVertex] = cost;
weightedGraph[currentVertex][visitedVer] = cost;
}
visitedSet.add(currentVertex);
for(Integer neighbourVert : adjacencyList[currentVertex]) {
if(neighbourVert != lastVisitedVertex) {
/*
* neighbourVert becomes currentVertex
* currentVertex becomes lastVisitedVertex
*/
allPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex);
}
}
}
}
Algorithm to compute sum of cost of all path between pair of unique vertices of a tree
Given tree is undirected graph. It has n vertices and n-1 edges. The algorithm should compute the sum of cost of all path between pair of unique vertices.
Thus, there are total nC2 or n(n-1)/2 such pairs. The time complexity of the mentioned algorithm is n(n-1)/2. Please suggest an algorithm with better space and time complexity if possible. Below is the pseudocode.
//Final Result
sumAllPair = 0;
//Total Number of vertices
N
//Adjacency List
adjacencyList: array of linked list
//Weighted Graph Matrix
weightedGraph: two dimensional integer array N*N
//Initialize Matrix
loop ii from 0 to N-1 {
loop jj from 0 to N-1 {
if(ii equals jj) {
weightedGraph[ii][jj] = 0
}else {
weightedGraph[ii][jj] = INFINITY
}
}
}
currentVertex = 0
visitedSet: LinkedHashSet of Size N
lastVisitedVertex = -1
call allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex)
print sumAllPair
/*
* Say graph has vertices 1,2,3,4,5,6,7
*
* allVertexPairSum() will compute sum of cost of all path between pair of unique vertices like this:
* 21 + (31+32) + (41+42+43) + (51+52+53+54) + (61+62+63+64+65)+(71+72+73+74+75+76)
* where ij represents cost of path from vertex i to vertex j
*
* Time Complexity:
* N(N-1)/2 or Combination(N,2)
*/
allVertexPairSum(weightedGraph, adjacencyList, currentVertex, visitedSet, lastVisitedVertex) {
for each visitedVer in visitedSet{
cost = weightedGraph[visitedVer][lastVisitedVertex] + weightedGraph[lastVisitedVertex][currentVertex]
sumAllPair = sumAllPair + cost
weightedGraph[visitedVer][currentVertex] = cost
weightedGraph[currentVertex][visitedVer] = cost
}
add currentVertex to visitedSet
for each neighbourVert in adjacencyList[currentVertex] {
if(neighbourVert not equals lastVisitedVertex) {
//neighbourVert becomes currentVertex
//currentVertex becomes lastVisitedVertex
allVertexPairSum(weightedGraph, adjacencyList, neighbourVert, visitedSet, currentVertex)
}
}
}
Here is an example: