• 973
• 1.7k
• 297.6k

# Road systems can be imagined as a graph of intersections connected

Mar 27 2023 6:18 AM

Hi Team

I need some help with my python program, basically the instruction is as below;

Write a function that takes as arguments:

• A string representing JSON graph of the road system
• The starting intersection (node)
• The ending intersection (node)

And returns a dictionary containing information about the shortest path.

The return value should be a dictionary with keys `distance` and `path`.

`distance` should be the number that is the total sum of the distance metadata on each edge used.

`path` should be a list of integers, where each number is the id of a node used along the path from the start to the end.

// Code to do this all with test cases, getting an error after compiling

``````
import json
from collections import deque
from typing import Dict, List, Tuple, Union

graph = {}
else:
raise ValueError("Invalid input format")
if src not in graph:
graph[src] = []
if dest not in graph:
graph[dest] = []

return graph

def navigate(roads: str, start: int, end: int) -> Dict[str, Union[int, List[int]]]:

if start not in graph or end not in graph:

distances = {node: float("inf") for node in graph}
previous_nodes = {node: None for node in graph}
distances[start] = 0

unvisited_nodes = set(graph)

while unvisited_nodes:
current_node = min(
unvisited_nodes, key=lambda node: distances[node]
)
unvisited_nodes.remove(current_node)

if distances[current_node] == float("inf"):
break

if alternative_route < distances[neighbor]:
distances[neighbor] = alternative_route
previous_nodes[neighbor] = current_node

path, current_node = [], end
while previous_nodes[current_node] is not None:
path.append(current_node)
current_node = previous_nodes[current_node]
if path:
path.append(start)

return {"distance": distances[end], "path": list(reversed(path))}

// test cases
{
"directed": false,
"nodes": [
{ "id": 0 },
{ "id": 1 },
{ "id": 2 },
{ "id": 3 },
{ "id": 4 },
{ "id": 5 },
{ "id": 6 },
{ "id": 7 },
{ "id": 8 },
{ "id": 9 }
],
"edges": [
{
"source": 1,
"target": 6,
"label": "Oak Street",
"distance": 5
}
},
{
"source": 6,
"target": 8,
"label": "Oak Street",
"distance": 6
}
},
{
"source": 8,
"target": 9,
"label": "Oak Street",
"distance": 11
}
},
{
"source": 8,
"target": 7,
"label": "Robin Way",
"distance": 3
}
},
{
"source": 7,
"target": 4,
"label": "Robin Way",
"distance": 5
}
},
{
"source": 6,
"target": 7,
"distance": 8
}
},
{
"source": 7,
"target": 9,
"distance": 9
}
},
{
"source": 4,
"target": 3,
"label": "National Street",
"distance": 6
}
},
{
"source": 1,
"target": 0,
"label": "Sunrise Drive",
"distance": 4
}
},
{
"source": 0,
"target": 3,
"label": "Short Street",
"distance": 3
}
},
{
"source": 5,
"target": 4,
"label": "Rickety Creek",
"distance": 7
}
},
{
"source": 4,
"target": 0,
"label": "Rickety Creek",
"distance": 5
}
},
{
"source": 9,
"target": 5,
"label": "Uphill Grove",
"distance": 6
}
},
{
"source": 5,
"target": 2,
"label": "Uphill Grove",
"distance": 5
}
},
{
"source": 2,
"target": 3,
"label": "Uphill Grove",
"distance": 7
}
}
]
}
"""

Test.assert_equals(navigate(roads, 1, 5), {'distance': 16, 'path': [ 1, 0, 4, 5 ]})
Test.assert_equals(navigate(roads, 6, 2), {'distance': 19, 'path': [ 6, 1, 0, 3, 2 ]})
Test.assert_equals(navigate(roads, 3, 4), {'distance': 6, 'path': [ 3, 4 ]})

// Error when compiling
ERROR: Traceback:
in <module>
in navigate