Optional Lecture 2: Goal-directed Dijkstra Algorithm

Loading...

Del curso dictado por University of California San Diego

Graph Analytics for Big Data

690 calificaciones

University of California San Diego

Graph Analytics for Big Data

690 calificaciones

Curso 5 de 6 en SpecializationBig Data

Want to understand your data network structure and how it changes under different conditions? Curious to know how to identify closely interacting clusters within a graph? Have you heard of the fast-growing area of graph analytics and want to learn more? This course gives you a broad overview of the field of graph analytics so you can learn new ways to model, store, retrieve and analyze graph-structured data. After completing this course, you will be able to model a problem into a graph database and perform analytical tasks over the graph in a scalable manner. Better yet, you will be able to apply these techniques to understand the significance of your data sets for your own projects.

De la lección

Graph Analytics

Optional Lecture 1: Bi-directional Dijkstra Algorithm2:00

Optional Lecture 2: Goal-directed Dijkstra Algorithm2:35

Optional Lecture 3: Power Law Graphs2:53

Optional Lecture 4: Measuring Graph Evolution3:41

Optional Lecture 5: Eigenvector Centrality6:47

Optional Lecture 6: Key Player Problems2:50

Conoce a los instructores

Amarnath Gupta
Director, Advanced Query Processing Lab
San Diego Supercomputer Center (SDSC)

So far we have seen two versions of the Dijkstra Algorithm.

Both these versions assume that the edge weights provided by the network

must be used as is.

Now that can lead to some interesting problems.

We saw one such problem before.

Remember we were trying to decide whether we should go from G to D or

from F to E because both options had the same total weight?

Now had we chosen to go from G to D,

it would take us a few extra steps to arrive at correct solution.

One way of handling this problem is to use additional knowledge.

So intuitively, we want to say that we know that we want to go to B.

So traversing through D is not a good idea.

Because it will take us away from B.

In other words we use the knowledge of the destination of B's location

to steer the direction of search.

This variant is called Goal-Directed Dijkstra Algorithm because

it is using the information about the target known at any point in the search.

The trick to use this information is to change the edge weights as we diverse.

How do we change the weight?

We use a formula, where the new weight

is the original weight together with a function called the potential function.

Now we'll show this in our example.

Since our graph is a proxy for

a road network, we can assume that we know the coordinates of every node.

Therefore, we can compute the distance between any two nodes.

In practice, we will choose a few nodes so

that we can compute the distance of every other node from these chosen nodes.

These chosen nodes are called landmarks.

Let's assume B, which is our target, is a landmark node, and

let's rewind to the state where we are trying to choose between

the GD expansion or the FE expansion.

So we calculate the distance of F, G and E from B.

BF is 20, BG is 80, and BE is 15.

Now we'll apply the formula like this.

For the FG case, we subtract the BF distance

from the weight and add the BD distance to the weight.

This gives us 70 because G is far from B.

Similarly for the FE case, we subtract the BF distance and

add the BE distance to the weight and it gives us 15.

Now, with these modified weights we choose the FE expansion.

In practice this significantly improves the actual performance of the algorithm.

So, this technique is used by many online mapping services when they give you

directions.

Explora nuestro catálogo

Inscríbete de manera gratuita y obtén recomendaciones personalizadas, actualizaciones y ofertas.

Coursera brinda acceso universal a la mejor educación del mundo, al asociarse con las mejores universidades y organizaciones, para ofrecer cursos en línea.

© 2019 Coursera Inc. Todos los derechos reservados.

Descargar en la App Store

Consíguelo en Google Play