Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Looking for K-Shortest Path High Level Pseudocode
New Posts  All Forums:Forum Nav:

# Looking for K-Shortest Path High Level Pseudocode

I'm trying to find a high level description of a k-shortest path algorithm such as Yen's.

For example, this is a high level description of Suurballe's algorithm:

Quote:
 Find the shortest path tree T rooted at node s by running Dijkstra's algorithm. This tree contains for every vertex u, a shortest path from s to u. Let P1 be the shortest cost path from s to t. The edges in T are called tree edges and the remaining edges are called non tree edges. Modify the cost of each edge in the graph by replacing the cost w(u,v) of every edge (u,v) by w'(u,v) = w(u,v) − d(s,v) + d(s,u). According to the resulting modified cost function, all tree edges have a cost of 0, and non tree edges have a non negative cost. Create a residual graph Gt formed from G by removing the edges of G that are directed into s and by reversing the direction of the zero length edges along path P1. Find the shortest path P2 in the residual graph Gt by running Dijkstra's algorithm. Discard the reversed edges of P2 from both paths. The remaining edges of P1 and P2 form a subgraph with two outgoing edges at s, two incoming edges at t, and one incoming and one outgoing edge at each remaining vertex. Therefore, this subgraph consists of two edge-disjoint paths from s to t and possibly some additional (zero-length) cycles. Return the two disjoint paths from the subgraph
A lot of the pseudocode I've been able to find for k-shortest assumes particular ways of defining graphs, paths, nodes, edges, etc and therefore they aren't very useful for what I need.
Bump, simply because I want to know what the hell is the OP is about
CPUGraphicsRAMOS
Core 2 Duo T7200 2.00 GHz 7900GS Go 2GB Win 7 Ultimate
Mouse
CPUGraphicsRAMOS
Core 2 Duo T7200 2.00 GHz 7900GS Go 2GB Win 7 Ultimate
Mouse
i couldnt find much on yen's algorithm but i believe the Floyd–Warshall algorithm is also a k shortest path algorithm. wikipedia has some good pseudo code for it. https://secure.wikimedia.org/wikiped...thm#Pseudocode

i hope this is what you're looking for. good luck with whatever you need this for
 Fractal Design (15 items) 775 4 life (15 items) Lenovo Thinkpad T410 Laptop (9 items)
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5
Mouse
Razor Abyssus
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ...
Power
9-cell plus Slice battery
 Fractal Design (15 items) 775 4 life (15 items) Lenovo Thinkpad T410 Laptop (9 items)
CPUMotherboardGraphicsRAM
Intel i7 2600K Biostar TP67XE NVidia GTX 570 Crucial Ballistix
Hard DriveHard DriveCoolingOS
Crucial C300 RealSSD SDD Samsung F4 2TB Noctua NH-D14 Windows 7 Professional x64
MonitorMonitorKeyboardPower
Asus VH202T 20'' 1600x900 Acer P244W 24" 1920 x 1080 Apple Keyboard with Numeric Keypad SeaSonic M12II 620W
CaseMouseAudio
Fractal Design Define XL Titanium Grey Razor Abyssus Creative Sound Blaster X-FI Xtreme Gamer
CPUMotherboardGraphicsRAM
Intel X3350 3.2Ghz @ 1.25v Gigabyte-GA-P35-DS3L (rev 2) XFX 4870 1GB 4GB OCZ Reaper PC2-6400
RAMHard DriveHard DriveOptical Drive
2GB Corsair XMS2 PC2-6400 Crucial C300 64GB SSD 2TB Samsung Spinpoint F4 Sony Super Multi
OSMonitorPowerCase
Windows 7 Professional x64 SP1 Asus VH202T 20'' 1600x900 SeaSonic M12II 620W Cooler Master Centurion 5
Mouse
Razor Abyssus
CPUMotherboardGraphicsRAM
Core i5-520M Lenovo 2522BF3 NVIDIA® Quadro® NVS3100M  Ramaxel Technology 4Gb DDR3
Hard DriveOptical DriveOSMonitor
Samsung SSD 128GB 1.8" Micro SATA  hl-dt-st dvdram gu10n Windows 7 Enterprise (64-bit) 14.1" WXGA (1280x800) display, anti-glare, LED ...
Power
9-cell plus Slice battery
I don't know about pseudocode, but I wrote this a couple of years ago:

Fair warning, this isn't pseudocode, it is complete code, C++.

http://pastebin.com/uQ2HNCAq
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
Quote:
 Originally Posted by travesty i couldnt find much on yen's algorithm but i believe the FloydÃ¢â‚¬â€œWarshall algorithm is also a k shortest path algorithm. wikipedia has some good pseudo code for it. https://secure.wikimedia.org/wikiped...thm#Pseudocode i hope this is what you're looking for. good luck with whatever you need this for
The Floyd-Warshall is just an all-pair shortest path algorithm.

Quote:
 Originally Posted by lordikon I don't know about pseudocode, but I wrote this a couple of years ago: Fair warning, this isn't pseudocode, it is complete code, C++. http://pastebin.com/uQ2HNCAq
Dijkstra's is also just a shortest path algorithm.

I'm looking for an algorithm that will find the k-shortest paths between a given source/destination pair.

So if k = 3, it would return the shortest path, the second shortest path, and the third shortest path.
Quote:
 Originally Posted by TEntel The Floyd-Warshall is just an all-pair shortest path algorithm. Dijkstra's is also just a shortest path algorithm. I'm looking for an algorithm that will find the k-shortest paths between a given source/destination pair. So if k = 3, it would return the shortest path, the second shortest path, and the third shortest path.
I see, I misunderstood the question. You might be able to modify the Dijkstra's to follow all paths rather than ignore longer paths, store the results, and return the top k results to you.
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
 Foldatron (17 items) Mat (10 items) Work iMac (9 items)
CPUMotherboardGraphicsGraphics
i7 950 EVGA x58 3-way SLI EVGA GTX 660ti GTX 275
RAMHard DriveHard DriveHard Drive
3x2GB Corsair Dominator DDR3-1600 80GB Intel X25-M SSD 2TB WD Black 150GB WD Raptor
Hard DriveOSMonitorKeyboard
2x 150GB WD V-raptor in RAID0 Win7 Home 64-bit OEM 55" LED 120hz 1080p Vizio MS Natural Ergonomic Keyboard 4000
PowerCase
750W PC P&C Silencer CoolerMaster 690
CPUGraphicsRAMHard Drive
Intel Core i5 2500S AMD 6770M 8GB (2x4GB) at 1333Mhz 1TB, 7200 rpm
Optical DriveOSMonitorKeyboard
LG 8X Dual-Layer "SuperDrive" OS X Lion 27" iMac screen Mac wireless keyboard
Mouse
Mac wireless mouse
CPUGraphicsRAMHard Drive
i7-2600K AMD 6970M 1GB 16GB PC3-10600 DDR3 1TB 7200rpm
Hard DriveOptical DriveOSMonitor
256GB SSD 8x DL "SuperDrive" OS X 10.7 Lion 27" 2560x1440 iMac display
Monitor
27" Apple thunderbolt display
Yeah, all k-path algorithms I've seen start by using Dijkstra's to find a shortest path tree from one node, to all other nodes. I already have code in place that does that.

There are plenty of journal / conference papers that deal with k-shortest path algorithms, but without understanding the general principle of k-shortest path, it is difficult to read the low-level mathematical explanations.
New Posts  All Forums:Forum Nav:
Return Home
Back to Forum: Coding and Programming
• Looking for K-Shortest Path High Level Pseudocode
Overclock.net › Forums › Software, Programming and Coding › Coding and Programming › Looking for K-Shortest Path High Level Pseudocode