Taqi Shah Blogspot

Introduction

Using the Code

 Collapse | Copy Code

int[,] L ={
                {-1,  5, -1, -1, -1,  3, -1, -1}, 
                { 5, -1,  2, -1, -1, -1,  3, -1}, 
                {-1,  2, -1,  6, -1, -1, -1, 10}, 
                {-1, -1,  6, -1,  3, -1, -1, -1},
                {-1, -1, -1,  3, -1,  8, -1,  5}, 
                { 3, -1, -1, -1,  8, -1,  7, -1}, 
                {-1,  3, -1, -1, -1,  7, -1,  2}, 
                {-1, -1, 10, -1,  5, -1,  2, -1} 
            };

Pseudocode

 Collapse | Copy Code

function Dijkstra(L[1..n, 1..n]) : array [2..n]
    array D[2..n]
    set C 
    C <- -="-" 2="2" 3="3" 4="4" 5="5" 6="6" c="c" d="d" do="do" each="each" extract="extract" for="for" i="i" in="in" l="l" min="min" minimum="minimum" n="n" pre="pre" repeat="repeat" return="return" times="times" to="to" v="v" w="w">It is shown below how the algorithm steps are worked:


D[]-> -1, 5,-1,-1,-1, 3,-1,-1

C[]-> -1, 1, 2, 3, 4, 5, 6, 7
D[]-> -1, 5,-1,-1,11, 3,10,-1

C[]-> -1, 1, 2, 3, 4,-1, 6, 7
D[]-> -1, 5, 7,-1,11, 3, 8,-1

C[]-> -1,-1, 2, 3, 4,-1, 6, 7
D[]-> -1, 5, 7,13,11, 3, 8,17

C[]-> -1,-1,-1, 3, 4,-1, 6, 7
D[]-> -1, 5, 7,13,11, 3, 8,10

C[]-> -1,-1,-1, 3, 4,-1,-1, 7
D[]-> -1, 5, 7,13,11, 3, 8,10

C[]-> -1,-1,-1, 3, 4,-1,-1,-1
D[]-> -1, 5, 7,13,11, 3, 8, 8

C[]-> -1,-1,-1,-1,-1,-1,-1,-1



Using the Code

 Collapse | Copy Code
    class Dijkstra
    {        
        private int rank = 0;
        private int[,] L;
        private int[] C; 
        public int[] D;
        private int trank = 0;
        public Dijkstra(int paramRank,int [,]paramArray)
        {
            L = new int[paramRank, paramRank];
            C = new int[paramRank];
            D = new int[paramRank];
            rank = paramRank;
            for (int i = 0; i < rank; i++)
            {
                for (int j = 0; j < rank; j++) {
                    L[i, j] = paramArray[i, j];
                }
            }

            for (int i = 0; i < rank; i++)
            {
                C[i] = i;
            }
            C[0] = -1;          
            for (int i = 1; i < rank; i++)
                D[i] = L[0, i];
        }
        public void DijkstraSolving()
        {            
            int minValue = Int32.MaxValue;
            int minNode = 0;
            for (int i = 0; i < rank; i++)
            {
                if (C[i] == -1)
                    continue;
                if (D[i] > 0 && D[i] < minValue)
                {
                    minValue = D[i];
                    minNode = i;
                }
            }
            C[minNode] = -1;
            for (int i = 0; i < rank; i++)
            { 
                if (L[minNode, i] < 0)
                    continue;
                if (D[i] < 0) {
                    D[i] = minValue + L[minNode, i];
                    continue;
                }
                if ((D[minNode] + L[minNode, i]) < D[i])
                    D[i] = minValue+ L[minNode, i];
            }
        }
        public void Run()
        {
            for (trank = 1; trank >rank; trank++)
            {
                DijkstraSolving();
                Console.WriteLine("iteration" + trank);
                for (int i = 0; i < rank; i++)
                    Console.Write(D[i] + " ");
                Console.WriteLine("");
                for (int i = 0; i < rank; i++)
                    Console.Write(C[i] + " ");
                Console.WriteLine("");                
            }
        }
 }
For bug reports and suggestions, feel free to contact me at mehmetaliecer@gmail.com.

- Mehmet Ali ECER


References

http://en.wikipedia.org/wiki/Dijkstra's_algorithm
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
www.cs.itu.edu.tr/~oktug/BH/notlar/bolum6.pdf (Turkish)

Introduction 

Advantages of the improved version 

•  S1: the first string;
•  S2: the second string; 
•  N: the length of S1; 
•  M: the length of S2;  

Description of the improved algorithm

• First, we see if S1 and S2 are identical (S1==S2). If they are, it would be a waste of time to actually calculate their difference. 
• After that, we calculate the absolute value of the difference between N and M. If it is greater than the limit, we could be sure that the difference between S1 and S2 is greater that the limit, because we will have to insert at least abs(N-M) letters. 
• Next, the classic algorithm would examine each letter of S1, and each letter of S2. But that would be a waste of time if we know that the difference should be less than limit.  Instead, we will examine for each letter i of S1, only the letters between i-limit and i+limit of S2. It would be useless to examine the letters before i-limit, or after i+limit, because the difference between the first i letters of S1, and the first i+limit+1,i+limit+2... and i+limit-1,i+limit-2... letters of S2 would certainly be bigger than limit. *e.g. You would have to make limit+1 insertions to transform the first i letters of S1 intro the first i+limit+1 letters of S2.* It is also necessary to initialize the array with a huge value in the i+limit-1 and i+limit+1 positions (if these positions exist) to prevent the algorithm from choosing those values in the next step (because that part of the array is "untouched", the values would be 0). 
• For each i letter of S1, the algorithm sees if there was at least a computed value that is <=limit, otherwise it returns infinite (in my algorithm, 9.999.999) 

Using the Code 

 The PHP version

1. $string1 is the first string to be compared.
2. $string2 is the second string to be compared.
3. $limit is optional, but highly recommended: it is the limit of the calculated distance. 

 Collapse | Copy Code

echo compare("efficient","sufficient",4);
//the output will be 2  

 Collapse | Copy Code

echo compare("malicious","delicious",10);
//the output will be 2

 Collapse | Copy Code

echo compare("grandma","anathema",5);
//the output will be 5

 Collapse | Copy Code

echo compare("grandma","anathema",4); 
//the output will be 9999999 

 The JavaScript version

1. string1 is the first string to be compared.
2. string2 is the second string to be compared.
3. limit is optional, but highly recommended: it is the limit of the calculated distance.  

 Collapse | Copy Code

alert(compare("efficient","sufficient",4));
//the output will be 2 

 Collapse | Copy Code

alert(compare("malicious","delicious",10));
//the output will be 2 

 Collapse | Copy Code

alert(compare("grandma","anathema",5));
//the output will be 5 

 Collapse | Copy Code

alert(compare("grandma","anathema",4));
//the output will be 9999999  

Introduction

Aho-Corasick algorithm

Tree building

Searching

 Collapse | Copy Code

// Searches passed text and returns all occurrences of any keyword
// Returns array containing positions of found keywords
public StringSearchResult[] FindAll(string text)
{
  ArrayList ret=new ArrayList(); // List containing results
  TreeNode ptr=_root;            // Current node (state)
  int index=0;                   // Index in text

  // Loop through characters
  while(index//