Posts Tagged ‘negative’
All Pair Shortest Path (APSP)
Question : Find shortest paths between all pairs of vertices in a graph.
Floyd-Warshall Algorithm
It is one of the easiest algorithms, and just involves simple dynamic programming. The algorithm can be read from this wikipedia page.
#define SIZE 31 #define INF 1e8 double dis[SIZE][SIZE]; void init(int N) { for (k=0;k<N;k++) for (i=0;i<N;i++) dis[i][j]=INF; } void floyd_warshall(int N) { int i,j,k; for (k=0;k<N;k++) for (i=0;i<N;i++) for (j=0;j<N;j++) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]); } int main() { //input size N init(N); //set values for dis[i][j] floyd_warshall(N); }
We can also use the algorithm to
- find the shortest path
- we can use another matrix called predecessor matrix to construct the shortest path.
- find negative cycles in a graph.
- If the value of any of the diagonal elements is less than zero after calling the floyd-warshall algorithm then there is a negative cycle in the graph.
- find transitive closure
- to find if there is a path between two vertices we can use a boolean matrix and use and-& and or-| operators in the floyd_warshall algorithm.
- to find the number of paths between any two vertices we can use a similar algorithm.
NJOY!!
-fR0DDY
Convert a number from decimal base to any Base
Convert a given decmal number to any other base (either positive or negative).
For example, 100 in Base 2 is 1100100 and in Base -2 is 110100100.
Here’s a simple algorithm to convert numbers from Decimal to Negative Bases :
def tonegativeBase(N,B): digits = [] while i != 0: i, remainder = divmod (i, B) if (remainder < 0): i, remainder = i + 1, remainder + B*-1 digits.insert (0, str (remainder)) return ''.join (digits)
We can just tweak the above algorithm a bit to convert a decimal to any Base. Here’s a sample code :
#include<iostream> using namespace std; void convert10tob(int N,int b) { if (N==0) return; int x = N%b; N/=b; if (x<0) N+=1; convert10tob(N,b); printf("%d",x<0?x+(b*-1):x); return; } int main() { int N,b; while (scanf("%d%d",&N,&b)==2) { if (N!=0) { convert10tob(N,b); printf("\n"); } else printf("0\n"); } }
NJOY!
-fR0DDY