Jump to content


Check out our Community Blogs

Register and join over 40,000 other developers!


Recent Status Updates

View All Updates

Photo
- - - - -

Floyd Warshall

shortest path

  • Please log in to reply
5 replies to this topic

#1 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 29 October 2009 - 04:25 PM

Lately, I've been doing some research on different graph algorithms to find the shortest path.

After researching Floyd-Warshall I found that it can generate the length of the shortest path. One question that I have is, is it possible to create what the actual path with Floyd Warshall If it is possible, any thoughts on how?

public static void floyd() {
        for (int i = 1; i <= nInter; i++) {
            for (int j = 1; j <= nInter; j++) {
                for (int y = 1; y <= nInter; y++) {

                    arnDelay[i][y] = Math.min(arnDelay[i][y],arnDelay[i][j] + arnDelay[j][y]);
                }
            }
        }
    }

  • 0

#2 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 02 November 2009 - 09:37 AM

Have each node in the graph store it's shortest path as well as the distance?
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#3 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 07 November 2009 - 05:38 PM

So, instead of having a 2d array of ints, I would have a 2d array of nodes? Is there any way you can manipulate the array of ints to backtrack through the path?

I have another question related to graphs; the adjacency matrix works for relatively small graphs but what do you do if you have a large number of nodes say 20000 nodes?

No way can you have a 2d array of 20000 * 20000 ints. :/
  • 0

#4 WingedPanther73

WingedPanther73

    A spammer's worst nightmare

  • Moderator
  • 17757 posts
  • Location:Upstate, South Carolina
  • Programming Language:C, C++, PL/SQL, Delphi/Object Pascal, Pascal, Transact-SQL, Others
  • Learning:Java, C#, PHP, JavaScript, Lisp, Fortran, Haskell, Others

Posted 07 November 2009 - 05:46 PM

I haven't studied graph algorithms much, but sparse arrays come to mind.
  • 0

Programming is a branch of mathematics.
My CodeCall Blog | My Personal Blog

My MineCraft server site: http://banishedwings.enjin.com/


#5 chili5

chili5

    CC Mentor

  • Expert Member
  • PipPipPipPipPipPipPipPip
  • 3038 posts
  • Programming Language:Java, C#, PHP, JavaScript, Ruby, Transact-SQL
  • Learning:C, Java, C++, C#, PHP, JavaScript, Ruby, Transact-SQL, Assembly, Scheme, Haskell, Others

Posted 09 November 2009 - 03:58 AM

I came up with this:

/**
 * UVA 10986
 *
 * Dijkstra's Algorithm
 *
 * The simpliest graph implementation is the adjacency matrix
 * but this isn't feasible for this problem since in the worst case
 * n = 19999 and there is no way you can have a 2d array of ints of size 19999 * 19999.
 *
 * My second approach used a map with an integer and linked list. This implementation
 * allows for bigger graphs but takes too long because you have to perform linear
 * searches to find vertices and to find the weight from v to i for every i.
 *
 * However; my program now successful solves the problem for the biggest input size
 * but not fast enough.
 */
package UVA;

import java.util.*;
import java.io.*;


public class email {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) throws IOException {
        graph g;
        int nCases;
        int nServers, nCables, nStart, nFinish;
        Scanner fin = new Scanner(new FileReader("email.txt"));
        //Scanner fin = new Scanner(System.in);
        int w, v, weight, nDist;
        int nCase = 1;

        nCases = fin.nextInt();

        for (int x = 0; x < nCases; x++) {
            nServers = fin.nextInt();
            nCables = fin.nextInt();
            nStart = fin.nextInt();
            nFinish = fin.nextInt();

            g = new graph(nServers);

            for (int i = 0; i < nCables; i++) {
                w = fin.nextInt();
                v = fin.nextInt();
                weight = fin.nextInt();
                g.addEdge(v, w, weight);
            }

            //g.outGraph();

            nDist = g.dijkstra(nStart, nFinish);

            System.out.println("Case #" + nCase + ": " + (nDist == -1 ? "unreachable" : nDist));
            nCase++;
        }

    }
}

class edge {

    int src;
    int dest;
    int weight;

    edge(int src, int dest, int w) {
        this.src = src;
        this.dest = dest;
        this.weight = w;
    }

    public String toString() {
        return dest + " ";
    }
}

class graph {

    int MAXV;
    HashMap<Integer, LinkedList<edge>> graph = new HashMap<Integer, LinkedList<edge>>(MAXV);

    graph(int v) {
        MAXV = v;
    }

    void addVertex(int v) {
        graph.put(v, new LinkedList<edge>());
    }

    void addEdge(int v, int w, int weight) {
        if (!graph.containsKey(v)) {
            addVertex(v);
        }

        if (!graph.containsKey(w)) {
            addVertex(w);
        }
        graph.get(v).add(new edge(v, w, weight));
        graph.get(w).add(new edge(w, v, weight));
    }

    void outGraph() {
        System.out.println(graph);
    }

    int dijkstra(int start, int finish) {
        boolean[] arbUsed = new boolean[MAXV + 1];
        int[] arnDist = new int[MAXV + 1];
        int v;
        int dist;
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(MAXV + 1);

        v = start;

        Arrays.fill(arnDist, 2000000);
        arnDist[start] = 0;

        pq.add(v);

        while (!pq.isEmpty()) {
            v = pq.remove();
            arbUsed[v] = true;


            /**
             * for each vertex v adjacent to u, v not in S
            {
            if d(v) > d(u) + [u,v]    // a shorter distance exists
            {
            d(v) = d(u) + [u,v]
            π(v) = u
            add v to Q
            }
            }
             */
            try {
                Iterator<edge> nodes = graph.get(v).iterator();
                // update all shortest paths from v
                while (nodes.hasNext()) {
                    // find the weight from v to i
                    edge nextEdge = nodes.next();
                    int i = nextEdge.dest;

                    int next = nextEdge.weight;

                    dist = arnDist[v] + next;
                    if (arnDist[i] > dist) {
                        arnDist[i] = dist;
                        pq.add(i);
                    }

                }
            } catch (NullPointerException ex) {
                return -1;
            }
        }

        return arnDist[finish];

    }
}

Basically I use a Map which holds a LinkedList of neighboring nodes. It isn't very efficient because to find a neighbor we have to an 0(n) search through the linked list. It helps that the table is based on a Hashtable though so i get 0(1) access to any node in the map. This approach works but not fast enough.

It has to be with LinkedLists, ArrayLists and Vector use up too much memory. Either my input is too slow or my Dijkstra's implementation isn't fast enough. I think it is both of them actually. :/ Another problem is that the program has to do a linear search to check if the node already exists because if we add a node the second time, the contents of the liinked list will be gone. :/
  • 0

#6 sourlemon

sourlemon

    CC Resident

  • Just Joined
  • PipPipPipPip
  • 93 posts

Posted 21 December 2009 - 07:58 PM

Are you looking for an algorithm for the shortest path between two nodes or any node?
  • 0





Also tagged with one or more of these keywords: shortest path

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download