CODEWITHSUNDEEP
javaalgorithmmatrixgraphgraph-theory
Nynaeve
Nynaeve

Reputation: 59

how to find if nodes are connected on a edge-weighted graph using adjacency matrix

I have a project that reads from an external file some statements and stores them into an weighted-edge directed graph using adjacency matrix. For example: A has B, C and D, B plus C, A and D, etc. When the program in the beginning reads the statements from the file, they are stored into two ArrayLists in the main class, one for the nodes and one for the edges. After some operations, all is added into the graph.

The problem I have now if how to check if the nodes in the graph are connected and if they are, how to display them, with their weights, in the main class. I heard that I can use Breadth-First Search or Depth-First Search but do not know how to implement them with weighted-edges and with nodes and edges that are made out of Strings and not Integers.

Upvotes: 0

Views: 418

Answers (1)

Vimal Bera
Vimal Bera

Reputation: 10497

The weighted version of BFS is called Dijkstra's algorithm. It is supposed to find the shortest paths from the origin to all other vertices. Pseudo code is given in wikipedia page and you can implement it from given pseudo code which will be much easier.

Upvotes: 2

Related Questions