void BellmanFord(graph *g, int s, int t)

latrellvie

Hallo liebe Kollegen, ich studiere begeistert Informatik (im 2ten Semester)und suche schon seit Tagen eine Lösung,beschäftige mich mit der ganzen Materie und mir ist das Verständnis wichtig. Den 2te Code - void BellmanFord( int s )- habe ich wie viele andere Codes auch aus dem Internet und ich nehme diesen als Ansatz da er für mich durchschaubar ist aber leider weiß ich nicht wie ich in so umforme, dass auch graph * g und int t als Funktionsparameter implementiert sind, also - void BellmanFord(graph *g, int s, int t)- .
Wer kann mir helfen... ???? Thx a lot !!!!

//
//  main.c
//  uebung7
//
//  Created by Me on 16.05.13.
//  Copyright (c) 2013 Me. All rights reserved.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES   8
#define INFINITE    0xffff

// structure for a node
typedef struct _node {
    int node;
    int cost;
    int updateFrom;
} node;

// structure for a graph defined by an adjacency matrix
typedef struct _graph {
    int numNodes;
    node nodes[MAX_NODES];
    int adjMatrix[MAX_NODES][MAX_NODES];
} graph;

// function prototypes
void initGraph(graph *g);
void resetGraph(graph *g);
int addNode(graph *g, char *name);
void BellmanFord(graph *g, int s, int t);

// initialize graph
void initGraph(graph *g) {
    int i, j;
    g->numNodes = 0;
    for (i = 0; i < MAX_NODES; i++) {
        g->nodes[i].node = 0;
        g->nodes[i].cost = INFINITE;
        g->nodes[i].updateFrom = 0;

        for (j = 0; j < MAX_NODES; j++) {
            g->adjMatrix[i][j] = 0;
        }
    }
}

// reset the colors to white and clear all times
void resetGraph(graph *g) {
    int i;
    for (i = 0; i < g->numNodes; i++) {
        g->nodes[i].node = 0;
        g->nodes[i].cost = INFINITE;
        g->nodes[i].updateFrom = 0;
    }
}

// add a node to the graph if it does not exist yet and return the index of the node
int addNode(graph *g, char * node) {
    int i;

    for (i = 0; i < g->numNodes; i++) {
        // if we find a node with the name return the index
        if (g->nodes[i].node == atoi(node)) {
            return i;
        }
    }

    g->nodes[atoi(node)-1].node = atoi(node);
    // increase the number of nodes since we added a new node
    g->numNodes++;

    return atoi(node)-1;
}

void BellmanFord(graph *g, int s, int t) {
    // TODO: implement BellmanFord
}

int main() {
    FILE *fp;
    char line[1000];
    char *pos;
    int i ,j= 0;

    // our graph g
    graph g;
    int source;
    int target;

    // initialize the new graph
    initGraph(&g);

    // open the file
    fp = fopen("graph", "r");
    if (fp == NULL) {
        printf("Cannot open Graphfile!!!\n");
        return -1;
    }

    // loop through all lines of the file
    while (!feof(fp)) {
        fgets(line, 1000, fp);

        // extract the first node name
        pos = strtok(line, " \n\r");
        // ignore any empty line
        if (pos == NULL) continue;

        // add the node to the graph
        source = addNode(&g, pos);

        // ignore the colon
        pos = strtok(NULL, " \n\r");

        // read all neighbor nodes including their edge weights on the same line
        while ((pos = strtok(NULL, " \n\r")) != NULL) {
            target = addNode(&g, pos);

            // get the weight of the node
            pos = strtok(NULL, " \n\r");

            // add an edge to the adjacency matrix
            g.adjMatrix[source][target] = atoi(pos);
            printf("[%d] -> [%d] with weight %d\n", g.nodes[source].node, g.nodes[target].node, atoi(pos));
        }
    }

    fclose(fp);

    // print adjacency matrix with weights
    printf("\n");

    for (i = 0; i < MAX_NODES; i++) {        
        for (j = 0; j < MAX_NODES; j++) {
            printf("%d",g.adjMatrix[i][j]);
        }
        printf("\n");
    }

    // Find the shortest path between node 1 and 8
    BellmanFord(&g, 0, 7);

    return 0;
}

void BellmanFord( int s ) {  /* muss hier natürlich wegen meiner Angabe auch graph * g und int t implementieren,also: void BellmanFord(graph *g, int s, int t) */
        int i, j;

        for (i = 0; i < n; ++i)
                d[i] = INFINITY;

        d[s] = 0;

        for (i = 0; i < n - 1; ++i)
                for (j = 0; j < e; ++j)
                        if (d[edges[j].u] + edges[j].w < d[edges[j].v])
                                d[edges[j].v] = d[edges[j].u] + edges[j].w;
}

das ist doch ganz einfach.
innerhalb der funktion machste

g->adjMatrix[source][target] = atoi(pos);
printf("[%d] -> [%d] with weight %d\n", g->nodes[source].node, g->nodes[target].node, atoi(pos));

usw.

latrellvie

Kannst du vielleicht den ganzen Code aufschreiben mit deiner Funktion inkludiert, dann sehe ich was ich falsch mache thx ... die Leiden eines Anfängers lol

latrellvie schrieb:

Kannst du vielleicht den ganzen Code aufschreiben mit deiner Funktion inkludiert, dann sehe ich was ich falsch mache thx ... die Leiden eines Anfängers lol

AHA ! Anscheind bist du ein fauler Hund ! Beschreib mal WAS du daran nicht verstehst und frag nicht nach einer Komplettlösung !

Für mich liest sich das so als wüsstest du nicht was dieses:
graph *g

Bedeutet ...

Google mal nach Strukturen !

Nein dafür geb ich dir keinen fertigen Code ! Ich war aufer Hauptschule (Kein Witz) und kenne auch das Wort Eigeninitiative !

BlackHatUndergroundHax0r) schrieb:

Für mich liest sich das so als wüsstest du nicht was dieses:
graph *g

Bedeutet ...

Das stammt doch von ihm (wenn ich das richtig lese)
Er weiß nicht, wie er das d[], edges[] .v .w .u darauf abbilden kann.