# Week 12 Sample Solution

## A. Search Algorithms

**Scenario: Siri is currently in Arad, and she wants to drive to Bucharest.**

<figure><img src="https://374096590-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FE6tM8okJTaOtct7O9mvr%2Fuploads%2FQCPRqd3iTBzPnytQiLXI%2Fimage.png?alt=media&#x26;token=57aabfcf-2b1d-4edf-a55a-dbdbc941f6f9" alt=""><figcaption></figcaption></figure>

1. **What is the solution for BFS?**

Arad->Sibiu->Fagaras->Bucharest

2. **What is the solution for A\*? The heuristic function is the straight-line distance to Bucharest.**

Arad->Sibiu->Rimnicu Vilcea->Pitesti->Bucharest

## B. Neo4j

### Task 2

**Write a `LOAD CSV` statement that imports the roads into your database. Remember, the Countries have already been created, so after `LOAD CSV` you'll need to run a `MATCH` statement to find the countries listed in each row of `roads.csv`, and only `CREATE` a road between those two countries. Don't forget the `distance` property, which should also be a float.**

```cypher
// Load data from CSV
LOAD CSV WITH HEADERS FROM "file:///roads.csv" AS row
MATCH (country1:Country), (country2:Country)
WHERE country1.name = row.country_1 AND country2.name = row.country_2
CREATE (country1)-[r:ROAD {distance: toFloat(row.distance)}]->(country2)
```

### Task 4

#### Task 4.1

**Change the query to be a depth-first search (DFS) and run it. Are the results the same, or different - and why?**

```cypher
// DFS
MATCH (source: Country {name: "Spain"})
CALL gds.dfs.stream("Countries", {
    sourceNode: source
    })
YIELD path
RETURN path
```

The results between BFS and DFS will differ in the order they visit nodes.

#### Task 4.2

**Try running the A\* source-target shortest path algorithm to find the shortest path between Spain and India.**

```cypher
#Clean the environment
CALL gds.graph.drop('Countries')

#Create a new project
CALL gds.graph.project('Transport','Country',{ROAD:{orientation: 'UNDIRECTED'}},
{relationshipProperties:'distance',
nodeProperties:['latitude','longitude']})

#Running the A* algorithm
MATCH (source: Country {name: 'Spain'}), (target: Country {name: 'India'})
CALL gds.shortestPath.astar.stream('Transport', {
    sourceNode: source,
    targetNode: target,
    latitudeProperty: 'latitude',
    longitudeProperty: 'longitude',
    relationshipWeightProperty: 'distance'
})
YIELD index, sourceNode, targetNode, totalCost, nodeIds, costs, path
RETURN
    index,
    gds.util.asNode(sourceNode).name AS sourceNodeName,
    gds.util.asNode(targetNode).name AS targetNodeName,
    totalCost,
    [nodeId IN nodeIds | gds.util.asNode(nodeId).name] AS nodeNames,
    costs,
    nodes(path) AS path
ORDER BY index
```

#### Task 4.3

**Create relationships of the type `MINST` between the Canada and every country reachable from Canada. Write a Cypher query to display the minimum spanning tree. Hint: the relationship type is `MINST`, not `ROAD`!**

```cypher
MATCH (c:Country{name:'Canada'})
CALL gds.beta.spanningTree.write('Transport', {
  sourceNode: id(c),
  relationshipWeightProperty: 'distance',
  writeRelationshipType: 'MINST',
  writeProperty: 'writeCost'
})
YIELD preProcessingMillis, computeMillis, writeMillis, effectiveNodeCount
RETURN preProcessingMillis,computeMillis, writeMillis, effectiveNodeCount;
```

```cypher
MATCH (c1:Country)-[m:MINST]->(c2:Country) RETURN c1, m, c2
```