freestuff.gr αρχική σελίδα
 FAQFAQ    ΑναζήτησηΑναζήτηση   Λίστα ΜελώνΛίστα Μελών   Ομάδες ΜελώνΟμάδες Μελών   <b>Εγγραφή Μέλους</b>Εγγραφή Μέλους 
 ΠροφίλΠροφίλ   Επιλογές μέλους Επιλογές   Τα bookmarks μου Τα bookmarks μου   Προσωπικά μηνύματαΠροσωπικά μηνύματα 
  διαφήμιση  

Καλώς ήρθατε στο forum μας! Για να συμμετάσχετε στις συζητήσεις θα πρέπει να είσαστε μέλος. Γίνετε μέλος τώρα!.

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


 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Moderators:  Super-Moderators, WebDev Moderators
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [7 Μηνύματα]      Bookmarks Tags: ψαχνω Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
ΑποστολέαςΜήνυμα
Herakles


Μέλος από: 17 Ιουλ 2004
Μηνύματα: 5

View users profile
ΜήνυμαΣτις: 22 Ιουλ 2005 12:39    Θέμα: Hi all ψάχνω για parallell floyd/warshall algorithm . Απάντηση με παράθεση  Mark this post and the followings unread

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

Μέλος από: 14 Απρ 2005
Βοηθήματα: 1
Μηνύματα: 256+


View users profile
ΜήνυμαΣτις: 22 Ιουλ 2005 13:03    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

Μέλος από: 05 Απρ 2003
Βοηθήματα: 2
Νέα: 2
Μηνύματα: 256+

Περιοχή: Πειραιάς
View users profile
portfolio facebook twitter skype 
ΜήνυμαΣτις: 22 Ιουλ 2005 13:03    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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::vector< std::vector<uint> > matrix;
#define INF ~0U

struct Edge {
  Edge *next;
  uint end;
  uint weight;
};

void floyd_warshall(std::vector<Edge*> graph) 
{
  uint i, j, k, size;
  Edge *iter;
  matrix dist;
  matrix pred;
 
  size = graph.size();
  dist.resize(size);
  pred.resize(size);
 
  /* Initialization */
  for(i = 0; i < size; ++i) {
    dist[i].resize(size);
    pred[i].resize(size);
    for(j = 0; j < size; ++j) {
      pred[i][j] = INF;
      if(i == j)
        dist[i][j] = 0;
      else
        dist[i][j] = INF;
    }
  }
 
  /* Import graph */
  for(i = 0; i < size; ++i) {
    iter = graph[i];
    while(iter) {
      dist[i][iter->end] = iter->weight;
      pred[i][iter->end] = i;
      iter = iter->next;
    }
  }
 
  /* Algorithm main loop */
  for(k = 0; k < size; ++k) {
    for(i = 0; i < size; ++i) {
      for(j = 0; j < size; ++j) {
        if(dist[i][k] == INF || dist[k][j] == INF)
          continue;
        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];
        }
      }
    }
  }
 
  // TODO: Do something with the results here
  // dist[i][j] is now the shortest distance between every two vertices, i and j,
  //            or INF if there is no such path
  // pred[i][j] == 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[i][j] + the edge from pred[i][j] to j
}

_________________
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


Μέλος από: 17 Ιουλ 2004
Μηνύματα: 5

View users profile
ΜήνυμαΣτις: 22 Ιουλ 2005 14:41    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

Μέλος από: 05 Απρ 2003
Βοηθήματα: 2
Νέα: 2
Μηνύματα: 256+

Περιοχή: Πειραιάς
View users profile
portfolio facebook twitter skype 
ΜήνυμαΣτις: 22 Ιουλ 2005 15:21    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

κώδικας:

#define INFINITY ((int) pow(2, sizeof(int)*8-2)-1)
typedef struct
{
         int weight;
         int dest;
} FWEdge;
typedef struct
{
         FWEdge* connections; // An array of edges which has this as the starting node
         int numconnect;
} FWVertice;
void print_path(int* predecessor, int nodecount, int i, int j, int fullstop = 0)
{
        if(i != j) print_path(predecessor, nodecount, i,predecessor[i*nodecount+j]);
        printf(", %i", j);
        if(fullstop) printf(".\n");
}
void FloydWarshall(FWVertice* vertices, int nodecount) // Vertices numbered
                                                       // from 0 to nodecount-1
{
        int* distances = (int*) malloc(nodecount*nodecount*sizeof(int)*8);
        int* predecessor = (int*) malloc(nodecount*nodecount*sizeof(int)*8);
        for(int i = 0; i < nodecount; i++)
        {
                for(int j = 0; j < nodecount; j++)
                {
                        distances[i*nodecount+j] = 0;
                        predecessor[i*nodecount+j] = i;
                }
        }
        for(int i = 0; i < nodecount; i++)
        {
                for(int j = 0; j < vertices[i].numconnect; j++)
                {
                        distances[i*nodecount + vertices[i].connections[j].dest] =
                            vertices[i].connections[j].weight;
                }
                for(int j = 0; j < nodecount; j++)
                {
                        if(!distances[i*nodecount+j] && (i^j))
                            // i ^ j returns 0 if they are equal
                        {
                                distances[i*nodecount+j] = INFINITY;
                        }
                }
        }
        for(int k = 0; k < nodecount; k++)
        {
                for(int i = 0; i < nodecount; i++)
                {
                        for(int j = 0; j < nodecount; j++)
                        {
                                if(distances[i*nodecount+j] >
                                      distances[i*nodecount+k] + distances[k*nodecount+j])
                                {
                                      distances[i*nodecount+j] =
                                        distances[i*nodecount+k] + distances[k*nodecount+j];
                                      predecessor[i*nodecount+j] =
                                        predecessor[k*nodecount+j];
                                }
                        }
                }
        }
        for(int i = 0; i < nodecount; i++)
        {
                for(int j = 0; j < nodecount; j++)
                {
                        printf("The shortest distances between nodes %i and %i is %i, "
                              "taking the path", i, j, distances[i*nodecount+j]);
                        print_path(predecessor, nodecount, i,j, 1);
                }
        }
}

_________________
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


Μέλος από: 17 Ιουλ 2004
Μηνύματα: 5

View users profile
ΜήνυμαΣτις: 22 Ιουλ 2005 16:11    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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

Μέλος από: 05 Απρ 2003
Βοηθήματα: 2
Νέα: 2
Μηνύματα: 256+

Περιοχή: Πειραιάς
View users profile
portfolio facebook twitter skype 
ΜήνυμαΣτις: 23 Ιουλ 2005 01:09    Θέμα: Απάντηση με παράθεση  Mark this post and the followings unread

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
Εμφάνιση Μηνυμάτων:   
Εισαγωγή νέου Θέματος   Απάντηση στο Θέμα Σελίδα 1 από 1 [7 Μηνύματα] Mark the topic unread :: Προηγούμενο θέμα :: Επόμενο θέμα
 Forum index » Δημιουργία Web Sites, Γραφικών & Προγραμματισμός » Γλώσσες Προγραμματισμού » C, C++
Τώρα είναι 21 Ιαν 2017 08:26 | All times are UTC + 2


Email This Page to Someone! add to Favorites

     Powered by p h p B B © 2001,2005 p h p B B Group
Για άμεση επικοινωνία με τον διαχειριστή του freestuff.gr στο email: freestuff.gr(παπάκι)gmail.com


Copyright © 1999-2013 Freestuff.gr All Rights Reserved  
Version Aegean, designed by N. Tsaganos