Η σελίδα μας αναβαθμίστηκε, γι' αυτό τον λόγο τα μέλη μας θα πρέπει να ζητήσουν νέο κωδικό πρόσβασης από την υπηρεσία "Αποστολή κωδικού πρόσβασης".
Εάν το email με τον νέο κωδικό δεν έρθει στο inbox κοιτάξτε και στο spam folder. Ο server είναι φρέσκος και δεν έχει το reputation που του αξίζει.

Hi all ψάχνω για parallell floyd/warshall algorithm .

Συζητήσεις για την γλώσσα C και C++

Συντονιστές: WebDev Moderators, Super-Moderators

Απάντηση
Herakles
Δημοσιεύσεις: 5
Εγγραφή: 17 Ιούλ 2004 12:50

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Herakles » 22 Ιούλ 2005 13:39

ξερει κανείς ρε παιδιά που θα το βρω;
thanks

Άβαταρ μέλους
shadow
Script Master
Δημοσιεύσεις: 606
Εγγραφή: 14 Απρ 2005 18:30

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από shadow » 22 Ιούλ 2005 14:03

Source code h pseudo-algorithm psaxneis?
Close your eyes
For your eyes will only tell the truth and the truth isnt what you want to see
In the dark, is it easy to pretend that the truth is it ought to be.
Programmers are programmers because they like to code

Άβαταρ μέλους
Rapid-eraser
WebDev Moderator
Δημοσιεύσεις: 6849
Εγγραφή: 05 Απρ 2003 17:50
Τοποθεσία: Πειραιάς
Επικοινωνία:

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Rapid-eraser » 22 Ιούλ 2005 14:03

Se psebdokodika

Κώδικας: Επιλογή όλων

function fw(int[0..n,0..n] graph) {
    // Initialization
    var int[0..n,0..n] dist := graph
    var int[0..n,0..n] pred
    for i from 0 to n
        for j from 0 to n
            if dist[i,j] > 0
                pred[i,j] := i
    // Main loop of the algorithm
    for k from 0 to n
        for i from 0 to n
            for j from 0 to n
                if dist[i,j] > dist[i,k] + dist[k,j]
                    dist[i,j] = dist[i,k] + dist[k,j]
                    pred[i,j] = pred[k,j]
    return dist
}

Kai eva implimentation se C++

Κώδικας: Επιλογή όλων

#include <vector>
typedef unsigned int uint;
typedef std&#58;&#58;vector< std&#58;&#58;vector<uint> > matrix;
#define INF ~0U

struct Edge &#123;
  Edge *next;
  uint end;
  uint weight;
&#125;;

void floyd_warshall&#40;std&#58;&#58;vector<Edge*> graph&#41;  
&#123;
  uint i, j, k, size;
  Edge *iter;
  matrix dist;
  matrix pred;
  
  size = graph.size&#40;&#41;;
  dist.resize&#40;size&#41;;
  pred.resize&#40;size&#41;;
  
  /* Initialization */
  for&#40;i = 0; i < size; ++i&#41; &#123;
    dist&#91;i&#93;.resize&#40;size&#41;;
    pred&#91;i&#93;.resize&#40;size&#41;;
    for&#40;j = 0; j < size; ++j&#41; &#123;
      pred&#91;i&#93;&#91;j&#93; = INF;
      if&#40;i == j&#41;
        dist&#91;i&#93;&#91;j&#93; = 0;
      else
        dist&#91;i&#93;&#91;j&#93; = INF;
    &#125;
  &#125;
  
  /* Import graph */
  for&#40;i = 0; i < size; ++i&#41; &#123;
    iter = graph&#91;i&#93;;
    while&#40;iter&#41; &#123;
      dist&#91;i&#93;&#91;iter->end&#93; = iter->weight;
      pred&#91;i&#93;&#91;iter->end&#93; = i;
      iter = iter->next;
    &#125;
  &#125;
  
  /* Algorithm main loop */
  for&#40;k = 0; k < size; ++k&#41; &#123;
    for&#40;i = 0; i < size; ++i&#41; &#123;
      for&#40;j = 0; j < size; ++j&#41; &#123;
        if&#40;dist&#91;i&#93;&#91;k&#93; == INF || dist&#91;k&#93;&#91;j&#93; == INF&#41;
          continue;
        if&#40;dist&#91;i&#93;&#91;j&#93; > dist&#91;i&#93;&#91;k&#93; + dist&#91;k&#93;&#91;j&#93;&#41; &#123;
          dist&#91;i&#93;&#91;j&#93; = dist&#91;i&#93;&#91;k&#93; + dist&#91;k&#93;&#91;j&#93;;
          pred&#91;i&#93;&#91;j&#93; = pred&#91;k&#93;&#91;j&#93;;
        &#125;
      &#125;
    &#125;
  &#125;
  
  // TODO&#58; Do something with the results here
  // dist&#91;i&#93;&#91;j&#93; is now the shortest distance between every two vertices, i and j,
  //            or INF if there is no such path
  // pred&#91;i&#93;&#91;j&#93; == i if the shortest path goes directly from i to j
  //            Otherwise the shortest path from i to j is made up of the 
  //            shortest path from i to pred&#91;i&#93;&#91;j&#93; + the edge from pred&#91;i&#93;&#91;j&#93; to j 
&#125;
Cu, Rapid-eraser, Tα αγαθά copies κτώνται.
Love is like oxygen, You get too much you get too high
Not enough and you're gonna die, Love gets you high

Herakles
Δημοσιεύσεις: 5
Εγγραφή: 17 Ιούλ 2004 12:50

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Herakles » 22 Ιούλ 2005 15:41

σε γλώσσα C ψάχνω παιδιά .Τhanks για τις μέχρι τωρα απαντήσεις

Άβαταρ μέλους
Rapid-eraser
WebDev Moderator
Δημοσιεύσεις: 6849
Εγγραφή: 05 Απρ 2003 17:50
Τοποθεσία: Πειραιάς
Επικοινωνία:

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Rapid-eraser » 22 Ιούλ 2005 16:21

Porting to C .......
...............................
...............................
...............................
DONE

Κώδικας: Επιλογή όλων

#define INFINITY &#40;&#40;int&#41; pow&#40;2, sizeof&#40;int&#41;*8-2&#41;-1&#41;
typedef struct
&#123;
         int weight;
         int dest;
&#125; FWEdge;
typedef struct
&#123;
         FWEdge* connections; // An array of edges which has this as the starting node
         int numconnect;
&#125; FWVertice;
void print_path&#40;int* predecessor, int nodecount, int i, int j, int fullstop = 0&#41;
&#123;
        if&#40;i != j&#41; print_path&#40;predecessor, nodecount, i,predecessor&#91;i*nodecount+j&#93;&#41;;
        printf&#40;", %i", j&#41;;
        if&#40;fullstop&#41; printf&#40;".\n"&#41;;
&#125;
void FloydWarshall&#40;FWVertice* vertices, int nodecount&#41; // Vertices numbered
                                                       // from 0 to nodecount-1
&#123;
        int* distances = &#40;int*&#41; malloc&#40;nodecount*nodecount*sizeof&#40;int&#41;*8&#41;;
        int* predecessor = &#40;int*&#41; malloc&#40;nodecount*nodecount*sizeof&#40;int&#41;*8&#41;;
        for&#40;int i = 0; i < nodecount; i++&#41;
        &#123;
                for&#40;int j = 0; j < nodecount; j++&#41;
                &#123;
                        distances&#91;i*nodecount+j&#93; = 0;
                        predecessor&#91;i*nodecount+j&#93; = i;
                &#125;
        &#125;
        for&#40;int i = 0; i < nodecount; i++&#41;
        &#123;
                for&#40;int j = 0; j < vertices&#91;i&#93;.numconnect; j++&#41;
                &#123;
                        distances&#91;i*nodecount + vertices&#91;i&#93;.connections&#91;j&#93;.dest&#93; = 
                            vertices&#91;i&#93;.connections&#91;j&#93;.weight;
                &#125;
                for&#40;int j = 0; j < nodecount; j++&#41;
                &#123;
                        if&#40;!distances&#91;i*nodecount+j&#93; && &#40;i^j&#41;&#41; 
                            // i ^ j returns 0 if they are equal
                        &#123;
                                distances&#91;i*nodecount+j&#93; = INFINITY;
                        &#125;
                &#125;
        &#125;
        for&#40;int k = 0; k < nodecount; k++&#41;
        &#123;
                for&#40;int i = 0; i < nodecount; i++&#41;
                &#123;
                        for&#40;int j = 0; j < nodecount; j++&#41;
                        &#123;
                                if&#40;distances&#91;i*nodecount+j&#93; > 
                                      distances&#91;i*nodecount+k&#93; + distances&#91;k*nodecount+j&#93;&#41;
                                &#123;
                                      distances&#91;i*nodecount+j&#93; = 
                                        distances&#91;i*nodecount+k&#93; + distances&#91;k*nodecount+j&#93;;
                                      predecessor&#91;i*nodecount+j&#93; =
                                        predecessor&#91;k*nodecount+j&#93;;
                                &#125;
                        &#125;
                &#125;
        &#125;
        for&#40;int i = 0; i < nodecount; i++&#41;
        &#123;
                for&#40;int j = 0; j < nodecount; j++&#41;
                &#123;
                        printf&#40;"The shortest distances between nodes %i and %i is %i, "
                              "taking the path", i, j, distances&#91;i*nodecount+j&#93;&#41;;
                        print_path&#40;predecessor, nodecount, i,j, 1&#41;;
                &#125;
        &#125;
&#125;
Cu, Rapid-eraser, Tα αγαθά copies κτώνται.
Love is like oxygen, You get too much you get too high
Not enough and you're gonna die, Love gets you high

Herakles
Δημοσιεύσεις: 5
Εγγραφή: 17 Ιούλ 2004 12:50

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Herakles » 22 Ιούλ 2005 17:11

thanks φιλε νασαι καλα .,αλλά δυστυχώς δεν ειναι parralel -εκεί είναι το προβλήμα μου-δεν μπορώ να το υλοποιήσω.-χρειάζεται χρήση pthreads

Άβαταρ μέλους
Rapid-eraser
WebDev Moderator
Δημοσιεύσεις: 6849
Εγγραφή: 05 Απρ 2003 17:50
Τοποθεσία: Πειραιάς
Επικοινωνία:

Hi all ψάχνω για parallell floyd/warshall algorithm .

Δημοσίευση από Rapid-eraser » 23 Ιούλ 2005 02:09

my bad dev to proseksa :)
Cu, Rapid-eraser, Tα αγαθά copies κτώνται.
Love is like oxygen, You get too much you get too high
Not enough and you're gonna die, Love gets you high

Απάντηση

Επιστροφή στο “C, C++”

Μέλη σε σύνδεση

Μέλη σε αυτήν τη Δ. Συζήτηση: Δεν υπάρχουν εγγεγραμμένα μέλη και 0 επισκέπτες