none
project RRS feed

  • Question

  • I am working on my project which is map routing and we should deal with a graph and this graph should be filled from a text file 

    I made my graph which is an Adjacency List of list of list the first list of type vertex (which is a class) and the second of type edge (another class) , I have to make an algorithm that return the shortest path and I decided to make it with a dijekstra algorithm 

    My question is I want to implement the dijekstra algorithm using list of list and I don't know how to implement it using my list of list graph 

    Thursday, December 13, 2018 10:30 PM

All replies

  • Hello,

    Check out the following GitHub Repo with example (there is C# and JavaScript so pick the right one)

    https://github.com/mburst/dijkstras-algorithm


    Please remember to mark the replies as answers if they help and unmark them if they provide no help, this will help others who are looking for solutions to the same or similar problem. Contact via my Twitter (Karen Payne) or Facebook (Karen Payne) via my MSDN profile but will not answer coding question on either.
    VB Forums - moderator
    profile for Karen Payne on Stack Exchange, a network of free, community-driven Q&A sites

    Thursday, December 13, 2018 10:38 PM
    Moderator
  • I am working on my project which is Map Routing , I am asked to implement a graph using adjacency list and fill it form a text file to get the data for the vertices and edges . I made my adjacency list from list of list the first list of type vertex (its a class) and the second one of type edge (another class) , then I have to get the shortest path for this graph and the most important factor is the time which is the weight of each edge .

    I want to get the shortest path using dijekstra algorithm but I don't know how to implement it using list of list .

    Thursday, December 13, 2018 10:44 PM
  • i tried a lot to make Dijkstra algorithm works with adjacency list but i failed xD 
    Thursday, December 13, 2018 10:55 PM
  • The usual way to do something like that is to build a graph, where each vertex node holds a list of its adjacent nodes.  Then, you traverse the graph starting at a node by putting the list of adjacent nodes, and the edge cost, into a queue.  For each node in that list, you add ITS adjacent nodes, except that you don't need to add any nodes you've already visited.  Eventually, all paths will either produce a cycle or reach your destination.

    Tim Roberts | Driver MVP Emeritus | Providenza & Boekelheide, Inc.

    Friday, December 14, 2018 12:51 AM
  • Hi Mary Mikhail,

    Thank you for posting here.

    For your question, if you want to get the shortest path using dijekstra algorithm c#, you could refer to the examples in the link below.

    https://www.csharpstar.com/dijkstra-algorithm-csharp/

    Best Regards,

    Wendy

    Note: This response contains a reference to a third-party World Wide Web site. Microsoft is providing this information as a convenience to you.
    Microsoft does not control these sites and has not tested any software or information found on these sites; Therefore, Microsoft cannot make any representations regarding the quality, safety, or suitability of any software or information found there.
    There are inherent dangers in the use of any software found on the Internet, and Microsoft cautions you to make sure that you completely understand the risk before retrieving any software from the Internet.


    MSDN Community Support
    Please remember to click "Mark as Answer" the responses that resolved your issue, and to click "Unmark as Answer" if not. This can be beneficial to other community members reading this thread. If you have any compliments or complaints to MSDN Support, feel free to contact MSDNFSF@microsoft.com.

    • Proposed as answer by Stanly Fan Monday, December 17, 2018 9:50 AM
    Friday, December 14, 2018 6:56 AM
    Moderator