Dijkstra's Algorithm

Hi guys: Can any one please tell me how to make a graph base on these values ? Thanks

X 2  3  X  2  4  X
   X  2  9  X  1  3
       X  X  2  2  2
           X  7  X  9
               X  2  X
                   X  1
                       X
mustish1Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

TommySzalapskiCommented:
The columns and rows represent nodes. So the first row is node 1 etc. If there is an X in the cell then the two nodes (row and column) are not directly connected. If there is a number, then that is the weight of the edge connecting them.

So node 1 is connected to nodes 2, 3, 5, and 6 with edges of 2, 3, 2, and 4 respectively.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
TommySzalapskiCommented:
The reason you only see numbers above the diagonal is because it is not a directed graph so saying node 1 connects to node 2 is the same as saying 2 connects to 1.
0
mustish1Author Commented:
     0  1  2  3  4  5  6
     ---------------------
0    X 2  3  X  2  4  X
1       X  2  9  X  1  3
2           X  X  2  2  2
3               X  7  X  9
4                   X  2  X
5                       X  1
6                           X


Do i need to assign a serial number?

For example the first number is X ? I am sorry i dont get it.
0
Cloud Class® Course: C++ 11 Fundamentals

This course will introduce you to C++ 11 and teach you about syntax fundamentals.

mustish1Author Commented:
Also node and vertex are same or not?
0
TommySzalapskiCommented:
Yes node=vertex.

Okay. Draw 7 vertices and label them 0-6. Then draw edges everywhere you see a number on the graph.
For example, on row 3 column 4 is a 7. So draw an edge from vertex 3 to vertex 4 and give it a weight of 7. Then just do that with the whole table.
0
mustish1Author Commented:
    0  1  2  3  4  5  6
     ---------------------
0    X 2  3  X  2  4  X
1       X  2  9  X  1  3
2           X  X  2  2  2
3               X  7  X  9
4                   X  2  X
5                       X  1
6                           X

I am not understanding if the shape of the graph can be a hexagone shape? or is it suppose to be a natural? some thing else
gr3.jpg
0
tliottaCommented:
if the shape of the graph can be a...

The "shape" is practically irrelevant at a technical detail level. The nodes could be in a straight line, around a circle or randomly placed on a page. It is the way the nodes are connected that is most important.

Of course, once connections are shown, it might be determined that a different arrangement is more practical and possibly more comprehensible.

Tom
0
mustish1Author Commented:
My basic graph is a hexagone but i am just confused the weights between the nodes compare to the answers given in the graph. I just cant seem to match them up correctly in order for to make sense. May be I am just not thinking in the way i need to think in order to comprehend the graph?
0
tliottaCommented:
   0  1  2  3  4  5  6
     ---------------------
0    X 2  3  X  2  4  X
1       X  2  9  X  1  3
2           X  X  2  2  2
3               X  7  X  9
4                   X  2  X
5                       X  1
6                           X

From that, I see that an edge connects nodes (0,1) with weight 2. I also see that you drew an edge between nodes 0 and 1 on your graph and that you marked it with "2". So far, so good.

But above I see that nodes (0,2) should be connected with an edge with weight 3. But you haven't drawn an edge between 0 and 2 on your graph. Instead, you continued the connection from node 1 to 2 and marked it with "1".

Do you see the difference?

Also above, I see that an edge should connect nodes (1,2) with weight 2. But you already drew an edge and marked it with "1".

Also above, I see that nodes (2,3) should not have an edge between them, since we see X in the table at that intersection. But your graph is drawn with an edge that is not marked. That edge shouldn't be there at all.

Is that making more sense?

Note that this should start to illustrate why the "shape isn't very relevant yet.

Tom
0
TommySzalapskiCommented:
The weight of an edge is NOT related at all to the length. If you are trying to draw a shape where all the numbers represent the length of the edges, then you will probably never get it to work.

You can draw them any way you like. Just put the right numbers in there. Drawing the points in a hexagon shape is just nice because it makes it easier to see all the lines. You can do it any way you like.

Note: Do not draw the whole hexagon. Just put the points there. 2 and 3 are not connected. Do not draw that edge.
0
mustish1Author Commented:
    0  1  2  3  4  5  6
     ---------------------
0    X 2  3  X  2  4  X
1    x  X  2  9  X  1  3
2    x  x  X  X  2  2  2
3    x  x  x  X  7  X  9
4    x  x  x  x   X  2  X
5    x  x  x  x   x   X  1
6    x  x  x  x   x   x  X

Can experts please tell me if there any mistake in it? Thanks.

new.jpg
0
mustish1Author Commented:
I miss 1,2
0
TommySzalapskiCommented:
Missing:
1,2=2
1,3=9


And your graph has 2 node 3s?
0
mustish1Author Commented:
2 nodes=2 vertices
what is 3s?
0
TommySzalapskiCommented:
3s means your graph has 2 vertices labelled 3. The one in the top left and one near the bottom right.
0
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Math / Science

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.