[jira] [Created] (SANDBOX-434) Implementing Johnson's algorihtm

classic Classic list List threaded Threaded
3 messages Options
Reply | Threaded
Open this post in threaded view
|

[jira] [Created] (SANDBOX-434) Implementing Johnson's algorihtm

ASF GitHub Bot (Jira)
Marco Speranza created SANDBOX-434:
--------------------------------------

             Summary: Implementing Johnson's algorihtm
                 Key: SANDBOX-434
                 URL: https://issues.apache.org/jira/browse/SANDBOX-434
             Project: Commons Sandbox
          Issue Type: New Feature
          Components: Graph
            Reporter: Marco Speranza


Provide an implementation of [Johnson's algorithm|http://en.wikipedia.org/wiki/Johnson's_algorithm].

here is the [pseudocode|http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif::600::349::/sites/dl/free/0070131511/25340/johnson.gif::JOHNSON]

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators: https://issues.apache.org/jira/secure/ContactAdministrators!default.jspa
For more information on JIRA, see: http://www.atlassian.com/software/jira

       
Reply | Threaded
Open this post in threaded view
|

[jira] [Updated] (SANDBOX-434) Implementing Johnson's algorihtm

ASF GitHub Bot (Jira)

     [ https://issues.apache.org/jira/browse/SANDBOX-434?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

Marco Speranza updated SANDBOX-434:
-----------------------------------

    Attachment: JohnsonAlgo.patch

Hi all,

I'm implementing the Johnson Algorithm but I need help. I created a testcase based on the wikipedia example (http://en.wikipedia.org/wiki/Johnson's_algorithm) but I experienced a problem:  the first step of Johnson algo is to create an augmentend graph with a new node connected with a 0-weighted edge  with other nodes, and after apply Belmann-Ford algo.

The problem is thet Belmann-Ford algo doesn't find the right shortest path.

can anyone see my implementation?

tnx a lot:-)
               

> Implementing Johnson's algorihtm
> ---------------------------------
>
>                 Key: SANDBOX-434
>                 URL: https://issues.apache.org/jira/browse/SANDBOX-434
>             Project: Commons Sandbox
>          Issue Type: New Feature
>          Components: Graph
>            Reporter: Marco Speranza
>            Assignee: Marco Speranza
>         Attachments: JohnsonAlgo.patch
>
>
> Provide an implementation of [Johnson's algorithm|http://en.wikipedia.org/wiki/Johnson's_algorithm].
> here is the [pseudocode|http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif::600::349::/sites/dl/free/0070131511/25340/johnson.gif::JOHNSON]

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira
Reply | Threaded
Open this post in threaded view
|

[jira] [Commented] (SANDBOX-434) Implementing Johnson's algorihtm

ASF GitHub Bot (Jira)
In reply to this post by ASF GitHub Bot (Jira)

    [ https://issues.apache.org/jira/browse/SANDBOX-434?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=13443943#comment-13443943 ]

Simone Tripodi commented on SANDBOX-434:
----------------------------------------

Hi Bro,

the main "mistake" is IMHO that

{code}
final Object sourceVertex = new Object();
{code}

is a un unknown element in whatever {{Graph}} instance, so a shortest path from {{sourceVertex}} to whatever doesn't exist.

You have to chose an element which is part of the domain of the input {{Graph}}.

HTH!
               

> Implementing Johnson's algorihtm
> ---------------------------------
>
>                 Key: SANDBOX-434
>                 URL: https://issues.apache.org/jira/browse/SANDBOX-434
>             Project: Commons Sandbox
>          Issue Type: New Feature
>          Components: Graph
>            Reporter: Marco Speranza
>            Assignee: Marco Speranza
>         Attachments: JohnsonAlgo.patch
>
>
> Provide an implementation of [Johnson's algorithm|http://en.wikipedia.org/wiki/Johnson's_algorithm].
> here is the [pseudocode|http://highered.mcgraw-hill.com/olcweb/cgi/pluginpop.cgi?it=gif::600::349::/sites/dl/free/0070131511/25340/johnson.gif::JOHNSON]

--
This message is automatically generated by JIRA.
If you think it was sent incorrectly, please contact your JIRA administrators
For more information on JIRA, see: http://www.atlassian.com/software/jira