本课程是面向有C语言经验的，并想要学习C++编程的程序员们。涉及到的例子和练习需要有对基础算法和面向对象软件的理解。
3.4 Using Dijkstra's Algorithm
Loading...
來自 University of California, Santa Cruz 的課程
C++ For C Programmers, Part A
388 個評分
從本節課中
Module 3
Point: Default constructor and initializing syntax. Conversion Constructors. Copy Constructor. List and dynamic memory allocation. Deep Copy.
與講師見面
Ira PohlProfessor
Computer Science
So, part of what the course is going to give you expertise in
is algorithmic graph theory, because it's a very, very good subject,
because graphs themselves are widgets, complicated widgets.
That have very different representations in many
ways to try and implement and get efficient
for particular different instances.
And so, we can see a lot of the old ideas and a lot of the uses of C++ effectively.
When we try to implement these algorithms in C++.
But also it gives you some background in doing further
and more complicated programs as this course (...)
progresses.
And one of the classical algorithms in computational, graph theory was invented
by the very famous Dutch mathematician and computer scientist Edsger Dijkstra.
So we're going to see how to use Dijkstra's algorithm and your homework is
going to be to implement Dijkstra's algorithm
and use it on a randomly generated
graph, which you'll also have to implement.
We'll also show you how to do a very similar but simpler
problem based on an algorithm that I invented many, many years ago.
Originally I implemented it in a much earlier programming language call PL-1.
And it's the problem of finding out whether a graph is a simple
connected component graph. And we're also
going to add some drawing lessons. We're going to be drawing
graphs as we go through and simulate these algorithms.
So this is the set of ideas we're going to need, to do the remaining homework.
in this class. So here's an unconnected graph and
that unconnected graph
is a graph of seven nodes. We might label
these nodes 0, 1, 2, 3, 4, 5, 6.
That would be traditional C labelling, namely we start from zero.
We might label these nodes, A, B, C, D. You'll see all these
labellings in the graph literature or might see them
as nodes on graph, maybe this is San Francisco.
And this is Los Angeles.
All of these are possible.
So I'm unconnected because we can't go from any node to any other node.
There's, we don't see any path.
Between, in this unconnected graph, between San Fransisco and Los Angeles.
We just see nodes.
Now, here's what we're going to show as a connected graph.
So I have left the
same labelling and now I'm going to add what are called edges.
So these blue lines are what we call as edges.
The little circles are nodes.
The little blue lines are edges. When you think of edges, think of roads.
So here's a road from San Francisco, going to Los Angeles.
For us who are Californians, that might be 101.
here's another road, from San Francisco to D.
Maybe D is San Jose.
Maybe this is San Diego. So
again, you have familiarity in the, in the ordinary world
with graphs. They're basically just road maps.
And they're road maps in which the cities are nodes and the highways are edges.
Now,
I'll draw a few more edges. If you looked at this connected graph.
The reason it's connected, is, I can find a path between any 2 of the cities.
And 2 of these nodes. Or, another term for nodes is vertices.
So if I want a path from San Francisco to San Diego, I'll use
this little wiggly line and show you here. Oh, there's a path.
So that whole graph is connected and indeed a single component.
Now, how can I get a computer to draw a graph?
Drawing a graph by computer is actually fairly efficient and the critical thing
will be to generate using a representation for the graph, an internal representation
a number of vertices, so we'll have to decide on the size of the graph.
And then we'll have to decide what edges will be placed in the graph.
And this particular algorithm I'm going to show
you, that'll generate a randomly generated graph.
We'll use the heap and create
a two-dimensional representation of the graph.
So let's see what that means.
The overall graph is going to be a pointer That ultimately stores boolean values.
What are boolean values?
They're the values true or false.
If I have a graph
that has edges, let's say they were like What we just saw, zero to 6.
And
I have true in one of the matrix entries. So let's say, in element 3, 4, I've stored
true.
This is going to mean that the edge from vertex three to four exists.
That's what's being created by this little routine.
The way it's created is, I seed the random number generator, I hope this
is all review, otherwise you'll have to
review how a pseudo-random number generator works.
I create a graph,
in this case, of the appropriate size. It's a graph that
is, has seven nodes.
And then, for each node, I have to
have a row, a Boolean row. So these are the rows.
That's what's being created here.
And then these are all capable of storing a Boolean value.
So the heap has allocated off the heap, through this for loop I've
created a two-dimensional array. Whose base pointer is graph.
And now,
I put edges in.
And I'm going to put edges in according to a density.
What do I mean by a density? The
density
is the probability an edge exists.
So that could be 0, or it could be up to 1.
That's what dense, the range of densities are.
0 would mean, that I'm never going to put (an edge in).
If, if this had been 0, no probability would be greater than 0, less than 0.
And so I'd never put in an edge. This is the act
of putting an edge
in. 0 would lead to no edges.
One would lead to every edge, the term here is complete.
A graph that has all its' edges, all its possible edges, is called complete.
So, we have a for loop . The for loop marches through the 2 dimensional graph,
if
i equals j that means if its on the diagonal we automatically put in false.
Otherwise and this is
symmetric this turns out to
be the undirected graph.
If the probability, in our case, we're looking at a density of point one nine.
So, roughly, one in five times I'm going to stick an edge in.
And, probability is just some function I'm computing
using the random number generator you may have to
review that, or you may have to look
at the code that's online for the probability function.
That will generate a randomly generated graph of the given density.
So, here's a few questions.
Density is zero. The graph has no, what?
Density is 1, the graph is what? The C word.
The density is fixed, say, to some size and the graph gets larger.
What can we say about it?
Likely it, how likely it is to be connected.
Take a second to look at that.
Okay.
As we just said already, zero means the calculation says, no chance.
You're never going to stick in an edge.
One means you're always going to stick an edge in.
So it's going to be a complete graph. And now, if the density is 0.1 and we have
a, a size that grows. So let's say we have five
nodes, density is one. 0.1 I should say.
0.1.
That means one tenth of the time in a five node graph, we're going to stick an edge.
Well, that's not going to happen often. Five nodes, that means roughly
speaking we're going to throw in an edge 50% of the time for that particular node.
Well,
that's not going to be connected, so it's very unlikely.
Let's say we go to a 50,000
node graph whose density is 0.1.
So if you're following me, the 50,000 node graph and
we have lots of 50,000 node graphs in the real world.
Just think of the map of all the cities in the United States.
And if you're thinking about the map of all the cities in the United States.
How many roads are there out of an individual city?
Maybe there's 20 rows out of an individual city, that might even be a big city.
So a density of 0.1 on a big map
is not all that, this would mean,
0.1 would mean that on average,
we're going to get 5,000 edges
per node. Here it was an average one half edge
per node.
When half edge per node for a small graph, it's going to leave us unconnected.
5,000 edges out of a 50,000 node graph is
going to leave us with a humongous number of paths
in that graph and it's very likely that, almost
certainly, with probability approaching 1, going to be connected.
So if you have a good intuition, about what we've been talking
about with these randomly generated graphs and this is going to come up
in the homework I'm assigning you, as the graphs get larger, namely
the number of vertices, the number of nodes in the graphs get larger.
Having a particular density makes it more and more
likely that there are paths between all the nodes.
