Shortest Path in a graph

Question

My graph is implemented in the following way:

struct node{
    string ID;
    vector<string> neighbors;

}

struct graph{
    vector<string> nodes;
}

nodes is a vector of nodes. Each node contains its ID and a vector of all of its neighbor's (Nodes it is pointing to) IDs

Is there a way I can apply Dijkstra's algorithm or Bellman-Ford to find the shortest path between two nodes? Find a duplicate cycle? How would I do that?

EDIT: sturcts were accidental named the same.

If that is an adjacency list you have - yes, it is possible. — Anirudh Ramanathan
Both your structs have the same name. Do you have a vector of node somewhere or something similar? Why don't you use a vector<node*> instead of vector<string> for neighbors? — user3072164
how do you retrieve a node, do you have a global map of id->node? — Ezra
Looking up elements will waste time with this kind of mapping. It should be easy to construct an adjacency list of vector<node*> as @Nabla suggested. — Anirudh Ramanathan

noooooooob noooooooob · Accepted Answer · 2014-01-28T06:44:14

You didn't mention anything about the edge weight.

Dijkstra algorithm works if you don't have a negative edge weight.

Bellman-ford algorithm works if you don't have a negative cycle. But you can also use Bellman-Ford algorithm to check if you have a negative cycle.

If it's a weightless edged-graph, you can just use BFS.

Shortest Path in a graph

1 Answers