Bellman-Ford in C (get the shortest path)

Multi tool use
Multi tool use












1














I want to use Bellman-Ford algorithm in C.



I tried a lot of times to print the shortest path but it doesn'twork, please wich code i can add in "//...not nompleted" area to do that in Bellman-Ford function.



Thanks you in advance.



enter image description here



I don't want to change my structures because i already did a lot of functions.
the structures of my project are :



typedef struct arc {
struct vertex *node;
struct arc *next;
}Arc;

typedef struct vertex {
int id ;
char libelle;
int color;
Arc *arcs;
struct vertex *next;
}Vertex;

typedef struct graphe {
Vertex *nodes;
int ** cost;
int nS; //number of vertex
}Graphe;


#

And this the Bellman function



void bellman(Graphe * g , char src , int d , int pi) {
//int d =>distance
//src => source
int V = g->nS;
int E = //..not completed
d[V];

int i,j;

// Step 1: Initialize distances from src to all other vertices as INFINITE

for (i = 0; i < V; i++)
d[i] = INFINY;

d[0] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
// to any other vertex can have at-most |V| - 1 edges

for (i = 1; i <= V-1; i++){

for (j = 0; j < E; j++){
//... not completed
//...

}

}


// Step 3: check for negative-weight cycles. The above step guarantees

// shortest distances if graph doesn't contain negative weight cycle.

// If we get a shorter path, then there is a cycle.

for (i = 0; i < E; i++){

//..not completed
//..
printf("Graph contains negative weight cycle");

}


printArr(d, V); //to print the path

}


Thans you so much in advance.










share|improve this question
























  • something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
    – bruno
    Dec 27 at 13:59








  • 1




    You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
    – John Bollinger
    Dec 27 at 14:25










  • Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
    – JSecurity
    Dec 27 at 15:20










  • 1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
    – Tim Randall
    Dec 27 at 15:51










  • I tried a lot of times but the shortest path doesn't shown
    – JSecurity
    Dec 27 at 16:55
















1














I want to use Bellman-Ford algorithm in C.



I tried a lot of times to print the shortest path but it doesn'twork, please wich code i can add in "//...not nompleted" area to do that in Bellman-Ford function.



Thanks you in advance.



enter image description here



I don't want to change my structures because i already did a lot of functions.
the structures of my project are :



typedef struct arc {
struct vertex *node;
struct arc *next;
}Arc;

typedef struct vertex {
int id ;
char libelle;
int color;
Arc *arcs;
struct vertex *next;
}Vertex;

typedef struct graphe {
Vertex *nodes;
int ** cost;
int nS; //number of vertex
}Graphe;


#

And this the Bellman function



void bellman(Graphe * g , char src , int d , int pi) {
//int d =>distance
//src => source
int V = g->nS;
int E = //..not completed
d[V];

int i,j;

// Step 1: Initialize distances from src to all other vertices as INFINITE

for (i = 0; i < V; i++)
d[i] = INFINY;

d[0] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
// to any other vertex can have at-most |V| - 1 edges

for (i = 1; i <= V-1; i++){

for (j = 0; j < E; j++){
//... not completed
//...

}

}


// Step 3: check for negative-weight cycles. The above step guarantees

// shortest distances if graph doesn't contain negative weight cycle.

// If we get a shorter path, then there is a cycle.

for (i = 0; i < E; i++){

//..not completed
//..
printf("Graph contains negative weight cycle");

}


printArr(d, V); //to print the path

}


Thans you so much in advance.










share|improve this question
























  • something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
    – bruno
    Dec 27 at 13:59








  • 1




    You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
    – John Bollinger
    Dec 27 at 14:25










  • Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
    – JSecurity
    Dec 27 at 15:20










  • 1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
    – Tim Randall
    Dec 27 at 15:51










  • I tried a lot of times but the shortest path doesn't shown
    – JSecurity
    Dec 27 at 16:55














1












1








1


1





I want to use Bellman-Ford algorithm in C.



I tried a lot of times to print the shortest path but it doesn'twork, please wich code i can add in "//...not nompleted" area to do that in Bellman-Ford function.



Thanks you in advance.



enter image description here



I don't want to change my structures because i already did a lot of functions.
the structures of my project are :



typedef struct arc {
struct vertex *node;
struct arc *next;
}Arc;

typedef struct vertex {
int id ;
char libelle;
int color;
Arc *arcs;
struct vertex *next;
}Vertex;

typedef struct graphe {
Vertex *nodes;
int ** cost;
int nS; //number of vertex
}Graphe;


#

And this the Bellman function



void bellman(Graphe * g , char src , int d , int pi) {
//int d =>distance
//src => source
int V = g->nS;
int E = //..not completed
d[V];

int i,j;

// Step 1: Initialize distances from src to all other vertices as INFINITE

for (i = 0; i < V; i++)
d[i] = INFINY;

d[0] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
// to any other vertex can have at-most |V| - 1 edges

for (i = 1; i <= V-1; i++){

for (j = 0; j < E; j++){
//... not completed
//...

}

}


// Step 3: check for negative-weight cycles. The above step guarantees

// shortest distances if graph doesn't contain negative weight cycle.

// If we get a shorter path, then there is a cycle.

for (i = 0; i < E; i++){

//..not completed
//..
printf("Graph contains negative weight cycle");

}


printArr(d, V); //to print the path

}


Thans you so much in advance.










share|improve this question















I want to use Bellman-Ford algorithm in C.



I tried a lot of times to print the shortest path but it doesn'twork, please wich code i can add in "//...not nompleted" area to do that in Bellman-Ford function.



Thanks you in advance.



enter image description here



I don't want to change my structures because i already did a lot of functions.
the structures of my project are :



typedef struct arc {
struct vertex *node;
struct arc *next;
}Arc;

typedef struct vertex {
int id ;
char libelle;
int color;
Arc *arcs;
struct vertex *next;
}Vertex;

typedef struct graphe {
Vertex *nodes;
int ** cost;
int nS; //number of vertex
}Graphe;


#

And this the Bellman function



void bellman(Graphe * g , char src , int d , int pi) {
//int d =>distance
//src => source
int V = g->nS;
int E = //..not completed
d[V];

int i,j;

// Step 1: Initialize distances from src to all other vertices as INFINITE

for (i = 0; i < V; i++)
d[i] = INFINY;

d[0] = 0;

// Step 2: Relax all edges |V| - 1 times. A simple shortest path from src
// to any other vertex can have at-most |V| - 1 edges

for (i = 1; i <= V-1; i++){

for (j = 0; j < E; j++){
//... not completed
//...

}

}


// Step 3: check for negative-weight cycles. The above step guarantees

// shortest distances if graph doesn't contain negative weight cycle.

// If we get a shorter path, then there is a cycle.

for (i = 0; i < E; i++){

//..not completed
//..
printf("Graph contains negative weight cycle");

}


printArr(d, V); //to print the path

}


Thans you so much in advance.







c graph path shortest






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Dec 27 at 15:17

























asked Dec 27 at 13:30









JSecurity

164




164












  • something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
    – bruno
    Dec 27 at 13:59








  • 1




    You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
    – John Bollinger
    Dec 27 at 14:25










  • Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
    – JSecurity
    Dec 27 at 15:20










  • 1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
    – Tim Randall
    Dec 27 at 15:51










  • I tried a lot of times but the shortest path doesn't shown
    – JSecurity
    Dec 27 at 16:55


















  • something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
    – bruno
    Dec 27 at 13:59








  • 1




    You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
    – John Bollinger
    Dec 27 at 14:25










  • Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
    – JSecurity
    Dec 27 at 15:20










  • 1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
    – Tim Randall
    Dec 27 at 15:51










  • I tried a lot of times but the shortest path doesn't shown
    – JSecurity
    Dec 27 at 16:55
















something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
– bruno
Dec 27 at 13:59






something wrong in int E = g->cout; , interrest of d[V]; alone ? in Graphe int ** cost; is very strange and probably wrong. Too tired to give addArc and addVertex ? Why you do not give us what you did rather than not completed even that doesn't work ? return; at end of a function i useless
– bruno
Dec 27 at 13:59






1




1




You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
– John Bollinger
Dec 27 at 14:25




You appear to be asking us to write an implementation of practically the whole algorithm -- certainly the all the key bits. That's far out of scope for SO. We will field questions about much more specific details of the program you write, but we generally will not do your work for you.
– John Bollinger
Dec 27 at 14:25












Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
– JSecurity
Dec 27 at 15:20




Sorry, I modified some lines. i juste want to get the shortest past using the structures, thanks you.
– JSecurity
Dec 27 at 15:20












1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
– Tim Randall
Dec 27 at 15:51




1. look at each path 2. calculate length of path 3. compare length with shortest length 4. remember new shortest length.... you should be able to write this in code using your variables and data structures.
– Tim Randall
Dec 27 at 15:51












I tried a lot of times but the shortest path doesn't shown
– JSecurity
Dec 27 at 16:55




I tried a lot of times but the shortest path doesn't shown
– JSecurity
Dec 27 at 16:55

















active

oldest

votes











Your Answer






StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");

StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});

function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});


}
});














draft saved

draft discarded


















StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53945907%2fbellman-ford-in-c-get-the-shortest-path%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown






























active

oldest

votes













active

oldest

votes









active

oldest

votes






active

oldest

votes
















draft saved

draft discarded




















































Thanks for contributing an answer to Stack Overflow!


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.





Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


Please pay close attention to the following guidance:


  • Please be sure to answer the question. Provide details and share your research!

But avoid



  • Asking for help, clarification, or responding to other answers.

  • Making statements based on opinion; back them up with references or personal experience.


To learn more, see our tips on writing great answers.




draft saved


draft discarded














StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53945907%2fbellman-ford-in-c-get-the-shortest-path%23new-answer', 'question_page');
}
);

Post as a guest















Required, but never shown





















































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown

































Required, but never shown














Required, but never shown












Required, but never shown







Required, but never shown







bQoJzLv6
FMO9F1,m b vAxnqJcecao9R,ICHWThrqJ,RF8hdzeo,i t Xel74d5 T 42XW

Popular posts from this blog

Monofisismo

Angular Downloading a file using contenturl with Basic Authentication

Olmecas