1
def dijikstra(start,goal):
    graph = {

        'a': {'b': 15, 'c': 13},
        'b': {'c': 12, 'd': 16},
        'c': {'d': 19, 'e': 21, 'b': 12},
        'd': {'e': 13, 'z': 17},
        'e': {'z': 16, 'd': 13},
        'z': {'d': 17}

    }
    shortest_distance = {}
    track_predecessor = {}
    unseen_nodes = graph
    infinity = 999999
    track_path = []


    for node in unseen_nodes:
        shortest_distance[node] = infinity

    shortest_distance[start] = 0

    while unseen_nodes:
        min_distance_node = None
        for node in unseen_nodes:
            if min_distance_node is None:
                min_distance_node = node
            elif shortest_distance[node] < shortest_distance[min_distance_node]:
                min_distance_node = node

        path_options = graph[min_distance_node].items()
        for child_node, weight in path_options:

            if weight+shortest_distance[min_distance_node]<shortest_distance[child_node]:
                shortest_distance[child_node] = weight+shortest_distance[min_distance_node]
                track_predecessor[child_node] = min_distance_node
        unseen_nodes.pop(min_distance_node)


    currentNode = goal

    while currentNode != start:
        try:
            track_path.insert(0,currentNode)
            currentNode = track_predecessor[currentNode]
        except KeyError:
            print('path is not reachable')
            break
    track_path.insert(0,start)

    if shortest_distance[goal] != infinity:
        print('For path ' + str(track_path))
        print("shortest distance is :" + str(shortest_distance[goal]))


dijikstra('a','z')

Here you can see the basic implementation of the Dijkstra's algorithm in python. By this we can get the shortest path. What I want to do here is finding the shortest path from source to end destination And also that path should go through given edges. as an example, going from a to z covering b and c so that it can achieve shortest path.

How to achieve this scenario by modifying this code

Jan Schultke
  • 17,446
  • 6
  • 47
  • 96
sandulasanth-7
  • 199
  • 1
  • 2
  • 14
  • Should it do through those intermediate edges in any order, or in a specific order? In case of the latter, just split the problem into finding a path from a to b, from b to c, and from c to z. – tobias_k Aug 24 '20 at 13:24
  • 1
    Look [Find the shortest path in a graph which visits certain nodes](https://stackoverflow.com/questions/222413/find-the-shortest-path-in-a-graph-which-visits-certain-nodes) – Aviv Yaniv Aug 24 '20 at 13:24
  • @tobias_k In any order so that it can achieve the shortest path. Plus it can be go through multiple nodes. Not just b and c – sandulasanth-7 Aug 24 '20 at 13:26
  • @UtherPendragon That's what the thread I sent you is about "...and passes through all of the 'mustpass' nodes (in any order)...". – Aviv Yaniv Aug 24 '20 at 13:27
  • @AvivYaniv Could you please point out where should I do the small change for this code. I'm bit new to python – sandulasanth-7 Aug 24 '20 at 13:35
  • @tobias_k Could you please point out where should I do the small change for this code. I'm bit new to python – sandulasanth-7 Aug 24 '20 at 13:35
  • If you want to visit the intermediate nodes in any order, it will be more than just a small change. See the answers in the linked question. – tobias_k Aug 24 '20 at 13:43
  • @tobias_k can I do something like this? [link](https://www.baeldung.com/cs/shortest-path-to-nodes-graph) – sandulasanth-7 Aug 24 '20 at 13:54
  • @tobias_k They suggest a change like this [link](https://www.baeldung.com/cs/wp-content/ql-cache/quicklatex.com-e4dcc87e7de9db7452161305790647c3_l3.svg) – sandulasanth-7 Aug 24 '20 at 13:55

0 Answers0