Bellman-Ford in C (get the shortest path)
![Multi tool use Multi tool use](http://sgv.ssvwv.com/sg/ssvwvcomimagb.png)
Multi tool use
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.
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
|
show 1 more comment
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.
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
something wrong inint E = g->cout;
, interrest ofd[V];
alone ? in Grapheint ** 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
|
show 1 more comment
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.
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
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.
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
c graph path shortest
edited Dec 27 at 15:17
asked Dec 27 at 13:30
JSecurity
164
164
something wrong inint E = g->cout;
, interrest ofd[V];
alone ? in Grapheint ** 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
|
show 1 more comment
something wrong inint E = g->cout;
, interrest ofd[V];
alone ? in Grapheint ** 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
|
show 1 more comment
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
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
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.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
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
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
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
something wrong in
int E = g->cout;
, interrest ofd[V];
alone ? in Grapheint ** 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