Finding the shortest path in a complex data structure with looping nodes

Question

Here is an example of the data structure I have stored in JSON:

{
    "alpha": {
        "node1": "echo",
        "node2": "bravo"
    },
    "bravo": {
        "node1": "alpha",
        "node2": "bravo",
        "node3": "charlie"
    },
    "charlie": {
        "node1": "bravo",
        "node2": "foxtrot"
    },
    "delta": {
        "node1": "alpha",
        "node2": "hotel"
    },
    "echo": {
        "node1": "golf",
        "node2": "delta"
    },
    "foxtrot": {
        "node1": "echo",
        "node2": "india",
        "node3": "delta"
    },
    "golf": {
        "node1": "hotel",
        "node2": "charlie"
    },
    "hotel": {
        "node1": "foxtrot",
        "node2": "india"
    },
    "india": {
        "node1": "charlie",
        "node2": "hotel"
    }
}

I am looking to find the shortest path between any two nodes. For example, the shortest path from echo to hotel is: echo -> golf -> hotel

As you can see, these nodes are looping and it's possible to traverse them endlessly. I should also note that the node paths are all one way. So using the same example above, the shortest path from hotel back to echo is: hotel -> foxtrot -> echo

Is there a name for a data structure like this? I know the looping breaks the rules of a "tree". Would this be graph traversal?

what have you tried? google "graph shortest path" gives you a few links regarding typical algorithms for that. — njzk2

user568109 user568109 · Accepted Answer · 2013-06-04T05:16:32

What you have is an adjacency list. Although it is cleaner to have something like this (removing node1, node2 to make it a simple array) :

{
    "alpha": [
        "echo",
        "bravo"
    ],
    "bravo": [
        "alpha",
        "bravo",
        "charlie"
    ],
    ...
    "india": [
        "charlie",
        "hotel"
    ]
}

There are no weights/distances given so you can find shortest path with BFS. Here is an implementation.

Finding the shortest path in a complex data structure with looping nodes

2 Answers