New question asked by user?

Question

This is new question asked by User

 

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



def parse_roads(roads) -> Dict[int, List[Tuple[int, Dict[str, float]]]]:
    graph = {}
    if isinstance(roads, str):
        roads = json.loads(roads)
    for road in roads:
        if isinstance(road, tuple):
            src, dest, distance = road
        elif isinstance(road, dict):
            src, dest, distance = road["src"], road["dest"], road["distance"]
        else:
            raise ValueError("Invalid input format")
        metadata = {"distance": distance}
        if src not in graph:
            graph[src] = []
        if dest not in graph:
            graph[dest] = []
        graph[src].append((dest, metadata))
        graph[dest].append((src, metadata))

    return graph

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

    if start not in graph or end not in graph:
        return {"error": "Starting or ending node not found 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

        for neighbor, metadata in graph[current_node]:
            alternative_route = distances[current_node] + metadata["distance"]
            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
roads = """
{
  "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",
      "metadata": {
        "distance": 5
      }
    },
    {
      "source": 6,
      "target": 8,
      "label": "Oak Street",
      "metadata": {
        "distance": 6
      }
    },
    {
      "source": 8,
      "target": 9,
      "label": "Oak Street",
      "metadata": {
        "distance": 11
      }
    },
    {
      "source": 8,
      "target": 7,
      "label": "Robin Way",
      "metadata": {
        "distance": 3
      }
    },
    {
      "source": 7,
      "target": 4,
      "label": "Robin Way",
      "metadata": {
        "distance": 5
      }
    },
    {
      "source": 6,
      "target": 7,
      "label": "Mountain Road",
      "metadata": {
        "distance": 8
      }
    },
    {
      "source": 7,
      "target": 9,
      "label": "Mountain Road",
      "metadata": {
        "distance": 9
      }
    },
    {
      "source": 4,
      "target": 3,
      "label": "National Street",
      "metadata": {
        "distance": 6
      }
    },
    {
      "source": 1,
      "target": 0,
      "label": "Sunrise Drive",
      "metadata": {
        "distance": 4
      }
    },
    {
      "source": 0,
      "target": 3,
      "label": "Short Street",
      "metadata": {
        "distance": 3
      }
    },
    {
      "source": 5,
      "target": 4,
      "label": "Rickety Creek",
      "metadata": {
        "distance": 7
      }
    },
    {
      "source": 4,
      "target": 0,
      "label": "Rickety Creek",
      "metadata": {
        "distance": 5
      }
    },
    {
      "source": 9,
      "target": 5,
      "label": "Uphill Grove",
      "metadata": {
        "distance": 6
      }
    },
    {
      "source": 5,
      "target": 2,
      "label": "Uphill Grove",
      "metadata": {
        "distance": 5
      }
    },
    {
      "source": 2,
      "target": 3,
      "label": "Uphill Grove",
      "metadata": {
        "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
   in parse_roads
ValueError: Invalid input format